perm filename CH1N2.XGP[206,LSP] blob
sn#235810 filedate 1976-09-07 generic text, type T, neo UTF8
/LMAR=0/XLINE=3/FONT#0=BASL30/FONT#1=BDR30/FONT#2=BASI30/FONT#3=BASB30/FONT#4=BDR30/FONT#5=SUB/FONT#6=SUP/FONT#9=FIX40/FONT#10=FIX30/FONT#11=GRFX25/FONT#12=GRFX35
␈↓ ↓H␈↓␈↓ εP␈↓ Oi
␈↓ ↓H␈↓␈↓ ∧P␈↓&T A B L E O F C O N T E N T S␈↓)αβ
␈↓ ↓H␈↓SECTION␈↓ PAGE
␈↓ ↓H␈↓I␈↓ α8INTRODUCTION TO LISP
␈↓ ↓H␈↓␈↓ βλ1␈↓ ∧(Lists.␈↓ ¬_∀∀∀∀∀∀∀∀∀∀∀∀␈↓ h␈↓ ? 1
␈↓ ↓H␈↓␈↓ βλ2␈↓ ∧(Atoms.␈↓ ¬_∀∀∀∀∀∀∀∀∀∀∀∀␈↓ h␈↓ ? 3
␈↓ ↓H␈↓␈↓ βλ3␈↓ ∧(List structures.␈↓ ¬x∀∀∀∀∀∀∀∀∀∀␈↓ h␈↓ ? 3
␈↓ ↓H␈↓␈↓ βλ4␈↓ ∧(S-expressions.␈↓ ¬x∀∀∀∀∀∀∀∀∀∀␈↓ h␈↓ ? 4
␈↓ ↓H␈↓␈↓ βλ5␈↓ ∧(The basic functions and predicates of LISP.␈↓ λx∀∀␈↓ h␈↓ ? 7
␈↓ ↓H␈↓␈↓ βλ6␈↓ ∧(Conditional expressions.␈↓ εX∀∀∀∀∀∀∀∀␈↓ h␈↓ ? 8
␈↓ ↓H␈↓␈↓ βλ7␈↓ ∧(Boolean expressions.␈↓ ε(∀∀∀∀∀∀∀∀∀␈↓ h␈↓ ? 9
␈↓ ↓H␈↓␈↓ βλ8␈↓ ∧(Recursive function definitions.␈↓ π8∀∀∀∀∀∀␈↓ h␈↓ 0 10
␈↓ ↓H␈↓␈↓ βλ9␈↓ ∧(Lambda expressions and functions with functions as
␈↓ ↓H␈↓␈↓ ¬(arguments.␈↓ ε(∀∀∀∀∀∀∀∀∀␈↓ h␈↓ 0 16
␈↓ ↓H␈↓␈↓ βλ10␈↓ ∧(Label.␈↓ ¬_∀∀∀∀∀∀∀∀∀∀∀∀␈↓ h␈↓ 0 18
␈↓ ↓H␈↓II␈↓ α8HOW TO WRITE RECURSIVE FUNCTION DEFINITIONS
␈↓ ↓H␈↓␈↓ βλ1␈↓ ∧(Static and dynamic ways of programming.␈↓ λH∀∀∀␈↓ h␈↓ 0 19
␈↓ ↓H␈↓␈↓ βλ2␈↓ ∧(Simple list recursion.␈↓ ε(∀∀∀∀∀∀∀∀∀␈↓ h␈↓ 0 20
␈↓ ↓H␈↓␈↓ βλ3␈↓ ∧(Simple S-expression recursion.␈↓ π8∀∀∀∀∀∀␈↓ h␈↓ 0 22
␈↓ ↓H␈↓␈↓ βλ4␈↓ ∧(Other structural recursions.␈↓ πλ∀∀∀∀∀∀∀␈↓ h␈↓ 0 23
␈↓ ↓H␈↓␈↓ βλ5␈↓ ∧(Tree search.␈↓ ¬H∀∀∀∀∀∀∀∀∀∀∀␈↓ h␈↓ 0 24
␈↓ ↓H␈↓␈↓ βλ6␈↓ ∧(Game trees.␈↓ ¬H∀∀∀∀∀∀∀∀∀∀∀␈↓ h␈↓ 0 28
␈↓ ↓H␈↓␈↓ εP␈↓ I1
␈↓ ↓H␈↓β␈↓ ¬yCHAPTER I
␈↓ ↓H␈↓β␈↓ ¬∞INTRODUCTION TO LISP
␈↓ ↓H␈↓1. ␈↓βLists.␈↓
␈↓ ↓H␈↓ Symbolic␈α
information␈α
in␈α∞LISP␈α
is␈α
expressed␈α
by␈α∞ S-expressions␈α
and␈α
these␈α∞ are␈α
represented
␈↓ ↓H␈↓in␈α∂ the␈α∂ memory␈α∞of␈α∂the␈α∂computer␈α∂by␈α∞list␈α∂structures.␈α∂Before␈α∞giving␈α∂formal␈α∂ definitions,␈α∂ we␈α∞ shall
␈↓ ↓H␈↓give some examples.
␈↓ ↓H␈↓ The most common form of S-expression is the list, and here are some lists:
␈↓ ↓H␈↓The list
␈↓ ↓H␈↓ ␈↓∧(A B C E)
␈↓ ↓H␈↓∧␈↓has four elements.
␈↓ ↓H␈↓The list
␈↓ ↓H␈↓ ␈↓∧(A B (C D) E)
␈↓ ↓H␈↓∧␈↓has four elements one of which is itself a list.
␈↓ ↓H␈↓The list
␈↓ ↓H␈↓ ␈↓∧(A)
␈↓ ↓H␈↓∧␈↓has one element.
␈↓ ↓H␈↓The list
␈↓ ↓H␈↓ ␈↓∧((A B C D))
␈↓ ↓H␈↓∧␈↓also has one element which itself is a list.
␈↓ ↓H␈↓The list
␈↓ ↓H␈↓ ␈↓∧()
␈↓ ↓H␈↓∧␈↓has no elements; it is also written
␈↓ ↓H␈↓ ␈↓∧NIL.
␈↓ ↓H␈↓∧␈↓The list
␈↓ ↓H␈↓ ␈↓∧(PLUS X Y)
␈↓ ↓H␈↓∧␈↓has three elements and may be used to represent the expression
␈↓ ↓H␈↓ ␈↓αx␈↓↓ + ␈↓αy.
␈↓ ↓H␈↓α␈↓The list
␈↓ ↓H␈↓ ␈↓∧(PLUS (TIMES X Y) X 3)
␈↓ ↓H␈↓∧␈↓has four elements and may be used to represent the expression
␈↓ ↓H␈↓ ␈↓αxy␈↓↓ + ␈↓αx␈↓↓ + ␈↓∧3.
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ I2
␈↓ ↓H␈↓∧␈↓The list
␈↓ ↓H␈↓ ␈↓∧(EXIST X (ALL Y (IMPLIES (P X) (P Y))))
␈↓ ↓H␈↓∧␈↓may be used to represent the logical expression
␈↓ ↓H␈↓ ␈↓↓(∃␈↓αx␈↓↓)(∀␈↓αy␈↓↓).␈↓αP␈↓↓(␈↓αx␈↓↓)⊃␈↓αP␈↓↓(␈↓αy␈↓↓).
␈↓ ↓H␈↓↓␈↓The list
␈↓ ↓H␈↓ ␈↓∧(INTEGRAL 0 ∞ (TIMES (EXP (TIMES I X Y)) (F X)) X)
␈↓ ↓H␈↓∧␈↓may be used to represent the expression
␈↓ ↓H␈↓ ␈↓ ␈ ␈↓αe␈↓εixy␈↓αf␈↓↓(␈↓αx␈↓↓)␈↓αdx.
␈↓ ↓H␈↓α␈↓The list
␈↓ ↓H␈↓ ␈↓∧((A B) (B A C D) (C B D E) (D B C E) (E C D F) (F E))
␈↓ ↓H␈↓is␈α
used␈α to␈α
represent␈α
the␈α network␈α
of␈α
Figure␈α 1␈α
according␈α
to␈α a␈α
scheme␈α
whereby␈α there␈α
is␈α
a␈α sublist
␈↓ ↓H␈↓for each vertex consisting of the vertex itself followed by the vertices to which it is connected.
␈↓"␈↓ ↓H␈↓ ␈↓ βX C
␈↓"∧␈↓ ↓H␈↓ ␈↓ βX ≤'~`≥
␈↓"␈↓ ↓H␈↓ ␈↓ βX ≤' ~ `≥
␈↓"␈↓ ↓H␈↓ ␈↓ βX B ≤' ~ `≥ E
␈↓"␈↓ ↓H␈↓ ␈↓ βX A ααααααααα' ~ `ααααααααα F␈↓ ↓H ≥ ≤
␈↓"␈↓ ↓H␈↓ ␈↓ βX `≥ ~ ≤'
␈↓"␈↓ ↓H␈↓ ␈↓ βX `≥ ~ ≤'
␈↓"␈↓ ↓H␈↓ ␈↓ βX `≥~≤'
␈↓"
␈↓ ↓H␈↓ ␈↓ βX D
␈↓"␈↓ ↓H␈↓ ␈↓ βX Figure 1
␈↓ ↓H␈↓ The␈α∞ elements␈α∞ of␈α∂ a␈α∞ list␈α∞ are␈α∂surrounded␈α∞by␈α∞parentheses␈α∞and␈α∂separated␈α∞by␈α∞spaces.␈α∂ A␈α∞list
␈↓ ↓H␈↓may␈α have␈α any␈α number␈α of␈α terms␈α and␈α any␈α of␈α these␈α terms␈α may␈α themselves␈α be␈α lists.␈α In␈α this␈α case,
␈↓ ↓H␈↓the␈α spaces␈α surrounding␈α a␈α
sublist␈α may␈α be␈α omitted,␈α and␈α
extra␈α spaces␈α between␈α elements␈α of␈α
a␈α list
␈↓ ↓H␈↓are allowed. Thus the lists
␈↓ ↓H␈↓ ␈↓∧(A B(C D) E)
␈↓ ↓H␈↓∧␈↓and
␈↓ ↓H␈↓ ␈↓∧(A B (C D) E)
␈↓ ↓H␈↓∧␈↓are regarded as the same.
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ I3
␈↓ ↓H␈↓2. ␈↓βAtoms.␈↓
␈↓ ↓H␈↓ The␈α expressions␈α ␈↓∧A,␈α B,␈α X,␈α Y,␈α 3,␈α PLUS,␈α ␈↓and␈α ␈↓∧ALL␈↓␈α occurring␈α in␈α the␈α above␈α lists␈α are␈α called␈α atoms.
␈↓ ↓H␈↓In␈α
general,␈α∞an␈α
atom␈α
is␈α∞expressed␈α
by␈α
a␈α∞sequence␈α
of␈α
capital␈α∞letters,␈α
digits,␈α
and␈α∞ special␈α
characters
␈↓ ↓H␈↓with␈α∩certain␈α∪ exclusions.␈α∩ The␈α∪exclusions␈α∩are␈α∩<space>,␈α∪<carriage␈α∩return>,␈α∪and␈α∩the␈α∪other␈α∩non-
␈↓ ↓H␈↓printing␈α
characters,␈α
and␈α
also␈α
the␈α
parentheses,␈α
brackets,␈α
semi-colon,␈α
and␈α
comma.␈α
Numbers␈α
are
␈↓ ↓H␈↓expressed␈α∃as␈α∃signed␈α∃decimal␈α∀or␈α∃octal␈α∃numbers,␈α∃ the␈α∀ exact␈α∃ convention␈α∃ depending␈α∃ on␈α∀ the
␈↓ ↓H␈↓implementation.␈α~ Floating␈α~ point␈α~ numbers␈α~ are␈α~ written␈α~ with␈α~decimal␈α~points␈α~and,␈α~when
␈↓ ↓H␈↓appropriate,␈α∪an␈α∪exponent␈α∪notation␈α∪depending␈α∪ on␈α∪ the␈α∪implementation.␈α∪ The␈α∪ reader␈α∩ should
␈↓ ↓H␈↓consult the programmer's manual for the LISP implementation he intends to use.
␈↓ ↓H␈↓ Some examples of atoms are
␈↓ ↓H␈↓ ␈↓∧THE-LAST-TRUMP
␈↓ ↓H␈↓∧␈↓ ␈↓∧A307B
␈↓ ↓H␈↓∧␈↓ ␈↓∧345
␈↓ ↓H␈↓∧␈↓ ␈↓∧3.14159,
␈↓ ↓H␈↓∧␈↓and from these we can form lists like
␈↓ ↓H␈↓ ((345 3.14159 -47) A307B THE-LAST-TRUMP -45.21).
␈↓ ↓H␈↓3. ␈↓βList structures.␈↓
␈↓ ↓H␈↓ Lists␈α
are␈α
represented␈α
in␈α
the␈α
memory␈α
of␈α
the␈α
computer␈α
by␈α
list␈α
structures.␈α
A␈α
list␈α
structure␈α is␈α
a
␈↓ ↓H␈↓collection␈α of␈α memory␈α words␈α each␈α of␈α which␈α is␈α divided␈α into␈α two␈α parts,␈α and␈α each␈α part␈α is␈α capable
␈↓ ↓H␈↓of␈α containing␈α an␈α address␈α in␈α memory.␈α The␈α two␈α parts␈α are␈α called␈α are␈α called␈α the␈α a-part␈α and␈α the␈α d-
␈↓ ↓H␈↓part.␈α⊂ There␈α⊃ is␈α⊂ one␈α⊃computer␈α⊂word␈α⊃for␈α⊂each␈α⊃element␈α⊂of␈α⊃the␈α⊂list,␈α⊃and␈α⊂the␈α⊃a-part␈α⊂of␈α⊃the␈α⊂word
␈↓ ↓H␈↓contains␈α⊂the␈α⊂ address␈α⊂of␈α⊂the␈α⊂list␈α⊂or␈α∂atom␈α⊂representing␈α⊂the␈α⊂element,␈α⊂and␈α⊂the␈α⊂d-part␈α⊂contains␈α∂the
␈↓ ↓H␈↓address␈α
of␈α
the␈α
word␈α
representing␈α
the␈α
next␈α
element␈α
of␈α
the␈α
list.␈α
If␈α
the␈α
list␈α
element␈α
is␈α
itself␈α
a␈α
list,
␈↓ ↓H␈↓then,␈α
of␈α
course,␈α
the␈α
address␈α
of␈α the␈α
first␈α
word␈α
of␈α
its␈α
list␈α
structure␈α is␈α
given␈α
in␈α
the␈α
a-part␈α
of␈α the␈α
word
␈↓ ↓H␈↓representing␈α
that␈α element.␈α
A␈α diagram␈α
shows␈α this␈α
more␈α clearly␈α
than␈α words,␈α
and␈α the␈α
list␈α structure
␈↓ ↓H␈↓corresponding␈α to␈α the␈α list␈α ␈↓∧(PLUS␈α (TIMES␈α X␈α Y)␈α X␈α 3)␈↓␈α which␈α may␈α represent␈α the␈α expression␈α ␈↓αxy␈↓↓␈α
+
␈↓ ↓H␈↓↓␈↓αx␈↓↓ + ␈↓∧3 is shown in figure 2.
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ I4
␈↓"␈↓ ↓H␈↓ ⊂αααπααα⊃ ⊂αααπααα⊃ ⊂αααπααα⊃ ⊂αααπααα⊃
␈↓"␈↓ ↓H␈↓ ααααα→~ ~ εαααα→~ ~ εαααα→~ ~ εαααα→~ ~ εααααααα⊃
␈↓"␈↓ ↓H␈↓ %απα∀ααα$ %απα∀ααα$ %απα∀ααα$ %απα∀ααα$ ~
␈↓"␈↓ ↓H␈↓ ↓ ~ ~ ↓ ~
␈↓"␈↓ ↓H␈↓ PLUS ~ ~ 3 ~
␈↓"␈↓ ↓H␈↓ ~ ⊂αααπααα⊃ ~ ⊂αααπααα⊃ ⊂αααπααα⊃ ~
␈↓"␈↓ ↓H␈↓ %α→~ ~ εααβα→~ ~ εαααα→~ ~ ~ ~
␈↓"␈↓ ↓H␈↓ %απα∀ααα$ ~ %απα∀ααα$ %απα∀απα$ ~
␈↓"␈↓ ↓H␈↓ ↓ ~ ~ ↓ ~ ~
␈↓"␈↓ ↓H␈↓ TIMES %απαα$ Y %ααπα$
␈↓"␈↓ ↓H␈↓ ↓ ↓
␈↓"␈↓ ↓H␈↓ X NIL
␈↓"␈↓ ↓H␈↓ Figure 2.
␈↓ ↓H␈↓∧␈↓ ␈↓∧Atoms␈α⊗ are␈α↔ represented␈α⊗ by␈α↔ the␈α⊗ addresses␈α⊗of␈α↔their␈α⊗property␈α↔lists␈α⊗which␈α↔are␈α⊗list
␈↓ ↓H␈↓∧structures␈α of␈α a␈α special␈α kind␈α depending␈α on␈α the␈α implementation.␈α (In␈α some␈α implementations,␈α the
␈↓ ↓H␈↓∧first␈α∪ word␈α∪ of␈α∪a␈α∪property␈α∪list␈α∪is␈α∪in␈α∪a␈α∪special␈α∪are␈α∪of␈α∪memory,␈α∪in␈α∪others␈α∪the␈α∪first␈α∀word␈α∪is
␈↓ ↓H␈↓∧distinguished␈α∂ by␈α∞ sign,␈α∂in␈α∞still␈α∂others␈α∞it␈α∂has␈α∂a␈α∞special␈α∂a-part.␈α∞ For␈α∂basic␈α∞LISP␈α∂programming,␈α∂it␈α∞is
␈↓ ↓H␈↓∧enough␈α
to␈α
know␈α
that␈α∞ atoms␈α
are␈α
distinguishable␈α
from␈α∞ other␈α
list␈α
structures␈α
by␈α∞a␈α
predicate
␈↓ ↓H␈↓∧called ␈↓βat␈↓.)
␈↓ ↓H␈↓ The␈α
last␈α
word␈α of␈α
a␈α
list␈α
cannot␈α have␈α
the␈α
address␈α of␈α
a␈α
next␈α
word␈α in␈α
its␈α
d-part␈α
since␈α there
␈↓ ↓H␈↓isn't any next word, so it has the address of a special atom called ␈↓∧NIL␈↓.
␈↓ ↓H␈↓ A␈α∪ list␈α∪ is␈α∪ referred␈α∪ to␈α∪ by␈α∪giving␈α∪the␈α∪address␈α∪of␈α∪its␈α∪first␈α∪element.␈α∪ According␈α∪to␈α∪this
␈↓ ↓H␈↓convention,␈α⊂we␈α∂see␈α⊂that␈α∂the␈α⊂a-part␈α∂ of␈α⊂ a␈α⊂list␈α∂ word␈α⊂ is␈α∂ the␈α⊂ list␈α∂ element␈α⊂ and␈α∂ the␈α⊂d-part␈α⊂is␈α∂a
␈↓ ↓H␈↓pointer␈α to␈α a␈α sublist␈α formed␈α by␈α deleting␈α the␈α first␈α element.␈α Thus␈α the␈α first␈α word␈α of␈α the␈α list␈α structure
␈↓ ↓H␈↓of␈α figure␈α 2␈α contains␈α a␈α pointer␈α to␈α the␈α list␈α structure␈α representing␈α the␈α atom␈α ␈↓∧PLUS␈↓,␈α while␈α its␈α d-part
␈↓ ↓H␈↓points␈α∂to␈α∂the␈α∞list␈α∂ ␈↓∧((TIMES␈α∂X␈α∞Y)␈α∂X␈α∂3)␈↓.␈α∞ The␈α∂second␈α∂word␈α∞contains␈α∂the␈α∂list␈α∂structure␈α∞representing
␈↓ ↓H␈↓␈↓∧(TIMES␈α∞X␈α
Y)␈↓␈α∞ in␈α∞ its␈α
a-part␈α∞ and␈α∞ the␈α
list␈α∞ structure␈α∞representing␈α
␈↓∧(X␈α∞3)␈↓␈α∞ in␈α
its␈α∞d-part.␈α∞ The␈α
last
␈↓ ↓H␈↓word␈α points␈α to␈α the␈α atom␈α ␈↓∧3␈↓␈α in␈α its␈α a-part␈α and␈α has␈α a␈α pointer␈α to␈α the␈α atom␈α ␈↓∧NIL␈↓␈α in␈α its␈α d-part.␈α This␈α is
␈↓ ↓H␈↓consistent with the convention that ␈↓∧NIL␈↓ represents the null list.
␈↓ ↓H␈↓4. ␈↓βS-expressions.␈↓
␈↓ ↓H␈↓ When␈α∂we␈α∂examine␈α⊂the␈α∂way␈α∂list␈α⊂structures␈α∂ represent␈α∂ lists␈α⊂ we␈α∂see␈α∂ a␈α⊂ curious␈α∂ asymmetry.
␈↓ ↓H␈↓Namely,␈α the␈α a-part␈α of␈α a␈α list␈α word␈α can␈α contain␈α an␈α atom␈α or␈α a␈α list,␈α but␈α the␈α d-part␈α can␈α contain␈α only␈α a
␈↓ ↓H␈↓list␈α∂ or␈α∂the␈α∞special␈α∂atom␈α∂ ␈↓∧NIL␈↓.␈α∂ This␈α∞restriction␈α∂is␈α∂quite␈α∂unnatural␈α∞from␈α∂the␈α∂computing␈α∂point␈α∞of
␈↓ ↓H␈↓view,␈α and␈α
we␈α shall␈α allow␈α
arbitrary␈α atoms␈α to␈α
inhabit␈α the␈α
d-parts␈α of␈α words,␈α
but␈α then␈α we␈α
must
␈↓ ↓H␈↓generalize␈α the␈α way␈α list␈α structures␈α are␈α expressed␈α as␈α character␈α strings.␈α To␈α do␈α this,␈α we␈α introduce␈α the
␈↓ ↓H␈↓notion of S-expression.
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ I5
␈↓ ↓H␈↓ An␈α∪ S-expression␈α∀is␈α∪either␈α∀an␈α∪atom␈α∀or␈α∪a␈α∪pair␈α∀of␈α∪S-expressions␈α∀separated␈α∪by␈α∀" . "␈α∪and
␈↓ ↓H␈↓surrounded by parentheses. In BNF, we can write
␈↓ ↓H␈↓<S-expression> ::= <atom> | (<S-expression> . <S-expression>).
␈↓ ↓H␈↓Examples of S-expressions are
␈↓ ↓H␈↓ ␈↓∧A
␈↓ ↓H␈↓∧␈↓ ␈↓∧(A . B)
␈↓ ↓H␈↓∧␈↓ ␈↓∧(A . (B . A))
␈↓ ↓H␈↓∧␈↓ ␈↓∧(PLUS (X . (Y . NIL)))
␈↓ ↓H␈↓∧␈↓ ␈↓∧(3 . 3.4)
␈↓ ↓H␈↓∧␈↓The␈α⊃spaces␈α⊃around␈α⊃the␈α⊃.␈α⊃may␈α⊃be␈α⊃ omitted␈α⊃ when␈α⊃ this␈α⊃ will␈α⊃ not␈α⊃ cause␈α⊃confusion.␈α∩ The␈α⊃only
␈↓ ↓H␈↓possible␈α∞confusion␈α
is␈α∞of␈α
the␈α∞dot␈α
separator␈α∞with␈α∞a␈α
decimal␈α∞point␈α
in␈α∞numbers.␈α
Thus,␈α∞in␈α∞the␈α
above
␈↓ ↓H␈↓cases,␈α
we␈α
may␈α∞ write␈α
␈↓∧(A.B),␈α
(A.(B.A))␈↓,␈α∞ and␈α
␈↓∧(PLUS.(X.(Y.NIL)))␈↓,␈α
but␈α∞if␈α
we␈α
wrote␈α∞␈↓∧(3.3.4)␈↓␈α
confusion
␈↓ ↓H␈↓would result.
␈↓ ↓H␈↓ In␈α∞the␈α∞memory␈α∞of␈α∞a␈α
computer,␈α∞an␈α∞S-expression␈α∞ is␈α∞ represented␈α
by␈α∞ the␈α∞ address␈α∞of␈α∞a␈α
word
␈↓ ↓H␈↓whose␈α
a-part␈α
contains␈α
the␈α
first␈α
element␈α
of␈α
the␈α
pair␈α
and␈α
whose␈α
d-part␈α
contains␈α
the␈α
second␈α
element
␈↓ ↓H␈↓of␈α
the␈α
pair.␈α
Thus,␈α
the␈α
S-expressions␈α ␈↓∧(A.B),␈α
(A.(B.A))␈↓,␈α
and␈α
␈↓∧(PLUS.(X.(Y.NIL)))␈α
␈↓␈α
are␈α represented
␈↓ ↓H␈↓by the list structures of figure 3.
␈↓"␈↓ ↓H␈↓ ⊂αααπααα⊃ ⊂αααπααα⊃ ⊂αααπααα⊃
␈↓"␈↓ ↓H␈↓ ~ ~ ~ ~ ~ εαααα→~ ~ ~
␈↓"␈↓ ↓H␈↓ %απα∀απα$ %απα∀ααα$ %απα∀απα$
␈↓"␈↓ ↓H␈↓ ↓ ↓ ~ ↓ ~
␈↓"␈↓ ↓H␈↓ A B ~ B ~
␈↓"␈↓ ↓H␈↓ ~ ~
␈↓"␈↓ ↓H␈↓ ~ ~
␈↓"␈↓ ↓H␈↓ %ααααααααπαααααααα$
␈↓"␈↓ ↓H␈↓ ↓
␈↓"␈↓ ↓H␈↓ A
␈↓"␈↓ ↓H␈↓ ⊂αααπααα⊃ ⊂αααπααα⊃ ⊂αααπααα⊃
␈↓"␈↓ ↓H␈↓ ~ ~ εαααα→~ ~ εαααα→~ ~ ~
␈↓"␈↓ ↓H␈↓ %απα∀ααα$ %απα∀ααα$ %απα∀απα$
␈↓"␈↓ ↓H␈↓ ↓ ↓ ↓ ↓
␈↓"␈↓ ↓H␈↓ PLUS X Y NIL
␈↓"␈↓ ↓H␈↓ Figure 3.
␈↓ ↓H␈↓ Note␈α that␈α the␈α list␈α ␈↓∧(PLUS␈α X␈α Y)␈↓␈α and␈α the␈α S-expression␈α ␈↓∧␈α (PLUS␈α .␈α (X␈α .␈α (Y␈α .␈α NIL)))␈↓␈α are␈α represented
␈↓ ↓H␈↓in␈α memory␈α by␈α the␈α same␈α list␈α structure.␈α The␈α simplest␈α way␈α to␈α treat␈α this␈α is␈α to␈α regard␈α S-expressions
␈↓ ↓H␈↓as␈α
primary␈α
and␈α
lists␈α∞ as␈α
abbreviations␈α
for␈α
certain␈α∞ S-expressions,␈α
namely␈α
those␈α
that␈α∞never␈α
have
␈↓ ↓H␈↓any␈α atom␈α but␈α NIL␈α
as␈α the␈α second␈α part␈α of␈α
a␈α pair.␈α In␈α giving␈α input␈α
to␈α LISP,␈α either␈α the␈α list␈α
form
␈↓ ↓H␈↓or␈α
the␈α S-expression␈α
form␈α
may␈α be␈α
used␈α for␈α
lists.␈α
On␈α output,␈α
LISP␈α will␈α
print␈α
a␈α list␈α
structure␈α
as␈α a
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ I6
␈↓ ↓H␈↓list␈α as␈α far␈α as␈α it␈α can,␈α otherwise␈α as␈α an␈α S-expression.␈α Thus,␈α some␈α list␈α structures␈α will␈α be␈α printed
␈↓ ↓H␈↓in a mixed notation, e.g. ␈↓∧((A . B) (C . D) (3))␈↓.
␈↓ ↓H␈↓ In␈α general,␈α the␈α
list␈α ␈↓↓(␈↓αa␈α b␈α
.␈α .␈α .␈α
z␈↓↓)␈↓␈α may␈α be␈α
regarded␈α as␈α an␈α
abbreviation␈α of␈α the␈α
S-expression␈α ␈↓↓(␈↓αa␈↓↓␈α .␈α
(␈↓αb␈↓↓
␈↓ ↓H␈↓↓. (␈↓αc␈↓↓ . (... (␈↓αz . ␈↓∧NIL␈↓↓) ...)))␈↓.
␈↓ ↓H␈↓ Exercises
␈↓ ↓H␈↓ 1. If we represent sums and products as indicated above and
␈↓ ↓H␈↓use␈α ␈↓∧(MINUS␈α X),␈α (QUOTIENT␈α X␈α Y)␈↓,␈α and␈α ␈↓∧(POWER␈α X␈α Y)␈↓␈α as␈α representations␈α of␈α ␈↓↓-␈↓αx␈↓,␈α ␈↓αx␈↓↓/␈↓αy␈↓,␈α and␈α ␈↓αx␈↓↓↑␈↓αy␈↓
␈↓ ↓H␈↓respectively, then
␈↓ ↓H␈↓ a. What do the lists
␈↓ ↓H␈↓ ␈↓∧(QUOTIENT 2 (POWER (PLUS X (MINUS Y)) 3))
␈↓ ↓H␈↓∧␈↓and
␈↓ ↓H␈↓ ␈↓∧(PLUS -2 (MINUS 2) (TIMES X (POWER Y 3.3)))
␈↓ ↓H␈↓∧␈↓represent?
␈↓ ↓H␈↓ b.␈α≥ How␈α≤ are␈α≥ the␈α≤ expressions␈α≥ ␈↓αxyz␈↓↓+␈↓∧3␈↓↓(␈↓αu␈↓↓+␈↓αv␈↓↓)↑(-␈↓∧3␈↓↓)␈↓␈α≤ and␈α≥␈↓↓(␈↓αxy␈↓↓-␈↓αyx␈↓↓)/(␈↓αxy␈↓↓+␈↓αyx␈↓↓)␈↓␈α≥to␈α≤be
␈↓ ↓H␈↓represented?
␈↓ ↓H␈↓ 2. In the above mentioned graph notation, what graph is represented by the list
␈↓ ↓H␈↓ ␈↓∧((A D E F)(B D E F)(C D E F)(D A B C)(E A B C)(F A B C))?
␈↓ ↓H␈↓∧␈↓ ␈↓∧␈↓3.␈α Write␈α the␈α list␈α ␈↓∧((PLUS␈α (TIMES␈α X␈α Y)␈α X␈α 3)␈↓␈α as␈α an␈α S-expression.␈α This␈α is␈α sometimes␈α referred␈α to
␈↓ ↓H␈↓as "dot-notation".
␈↓ ↓H␈↓ 4. Write the following S-expressions in list notation to whatever extent is possible:
␈↓ ↓H␈↓ a. (A . NIL)
␈↓ ↓H␈↓ b. (A . B)
␈↓ ↓H␈↓ c. ((A . NIL) . B)
␈↓ ↓H␈↓ d. ((A . B) . ((C . D) . NIL).
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ I7
␈↓ ↓H␈↓5. ␈↓βThe basic functions and predicates of LISP.␈↓
␈↓ ↓H␈↓ Just␈α∂as␈α∂numerical␈α∂computer␈α∂programs␈α⊂are␈α∂ based␈α∂ on␈α∂ the␈α∂ four␈α∂arithmetic␈α⊂ operations␈α∂ of
␈↓ ↓H␈↓addition␈α⊂subtraction,␈α⊃multiplication,␈α⊂and␈α⊃division,␈α⊂and␈α⊃the␈α⊂arthmetic␈α⊃predicates␈α⊂of␈α⊃equality␈α⊂and
␈↓ ↓H␈↓comparison,␈α⊂so␈α⊂symbolic␈α⊂ computation␈α⊂ has␈α⊂ its␈α⊂basic␈α⊂predicates␈α⊂and␈α⊂functions.␈α⊂ LISP␈α⊃has␈α⊂three
␈↓ ↓H␈↓basic functions and two predicates.
␈↓ ↓H␈↓ First,␈α we␈α have␈α two␈α functions␈α ␈↓βa␈↓␈α and␈α ␈↓βd␈↓.␈α ␈↓βa␈α ␈↓αx␈↓␈α is␈α the␈α a-part␈α of␈α the␈α S-expression␈α ␈↓∧x␈↓.␈α Thus,␈α ␈↓βa␈↓∧(A␈α .
␈↓ ↓H␈↓∧B)␈α ␈↓↓=␈α ␈↓∧A␈↓,␈α and␈α
␈↓βa␈↓∧((A␈α .␈α B)␈α .␈α
A)␈α ␈↓↓=␈α ␈↓∧(A␈α .␈α
B)␈↓.␈α ␈↓βd␈α ␈↓αx␈↓␈α is␈α
the␈α d-part␈α of␈α the␈α
S-expression␈α ␈↓αx␈↓.␈α Thus␈α ␈↓βd␈↓∧(A␈α
.␈α B)␈α ␈↓↓=␈α ␈↓∧B␈↓,␈α
and
␈↓ ↓H␈↓␈↓βd␈↓∧((A␈α
.␈α
B)␈α .␈α
A)␈α
␈↓↓=␈α ␈↓∧A␈↓.␈α
␈↓βa␈α
␈↓αx␈↓␈α and␈α
␈↓βd␈α
␈↓αx␈↓␈α are␈α
undefined␈α
in␈α basic␈α
LISP␈α
when␈α ␈↓αx␈↓␈α
is␈α
an␈α atom,␈α
but␈α
they␈α may␈α
have
␈↓ ↓H␈↓a meaning in some implementations.
␈↓ ↓H␈↓ Since␈α
lists␈α
are␈α a␈α
particular␈α
kind␈α
of␈α S-expression,␈α
the␈α
meanings␈α
of␈α ␈↓βa␈↓␈α
and␈α
␈↓βd␈↓␈α
for␈α lists␈α
are
␈↓ ↓H␈↓also determined by the above definitions. Thus, we have
␈↓ ↓H␈↓ ␈↓βa␈↓∧(A B C D) ␈↓↓=␈↓β A
␈↓ ↓H␈↓β␈↓and
␈↓ ↓H␈↓ ␈↓βd␈↓∧(A B C D) ␈↓↓= ␈↓∧(B C D),
␈↓ ↓H␈↓∧␈↓and␈α we␈α see␈α that,␈α in␈α general,␈α ␈↓βa␈α ␈↓αx␈↓␈α is␈α the␈α first␈α element␈α of␈α the␈α list␈α ␈↓αx␈↓,␈α and␈α ␈↓βd␈α ␈↓αx␈↓␈α is␈α the␈α rest␈α of␈α the␈α list,
␈↓ ↓H␈↓deleting that first element.
␈↓ ↓H␈↓ Notice␈α
that␈α∞ for␈α
S-expressions,␈α
the␈α∞definitions␈α
of␈α
␈↓βa␈α∞␈↓αx␈↓␈α
and␈α
␈↓βd␈α∞␈↓αx␈↓␈α
are␈α
symmetrical,␈α∞while␈α
for
␈↓ ↓H␈↓lists␈α∞the␈α∞symmetry␈α∞is␈α∞lost.␈α
This␈α∞is␈α∞because␈α∞ of␈α∞ the␈α
unsymmetrical␈α∞nature␈α∞of␈α∞the␈α∞convention␈α
that
␈↓ ↓H␈↓defines lists in terms of S-expressions.
␈↓ ↓H␈↓ Notice,␈α
further,␈α
our␈α
convention␈α
of␈α∞ writing␈α
␈↓βa␈↓␈α
and␈α
␈↓βd␈↓ ␈α
without␈α∞ brackets␈α
surrounding
␈↓ ↓H␈↓the␈α argument.␈α
Also,␈α we␈α
use␈α lower␈α case␈α
letters␈α for␈α
our␈α function␈α names␈α
and␈α for␈α
variables,␈α reserving
␈↓ ↓H␈↓the upper case letters for the S-expressions themselves.
␈↓ ↓H␈↓ The␈α third␈α function␈α ␈↓αcons␈↓↓[␈↓αx␈↓↓,␈α ␈↓αy␈↓↓]␈↓␈α forms␈α the␈α S-expression␈α whose␈α a-part␈α and␈α d-part␈α are␈α ␈↓αx␈↓␈α and
␈↓ ↓H␈↓␈↓αy␈↓ respectively. Thus
␈↓ ↓H␈↓ ␈↓αcons␈↓↓[␈↓∧(A.B), A␈↓↓] = ␈↓∧((A.B).A).
␈↓ ↓H␈↓∧␈↓ ␈↓∧␈↓We␈α⊂ see␈α⊂ that␈α⊂ for␈α⊂ lists,␈α⊂ ␈↓αcons␈↓␈α⊂ is␈α⊂a␈α⊂prefixing␈α⊂operation.␈α⊂ Namely,␈α⊂ ␈↓αcons␈↓↓[␈↓αx␈↓↓,␈α⊂␈↓αy␈↓↓]␈↓␈α⊂ is␈α⊃the␈α⊂list
␈↓ ↓H␈↓obtained by putting the element ␈↓αx␈↓ onto the front of the list ␈↓αy␈↓. Thus
␈↓ ↓H␈↓ ␈↓αcons␈↓↓[␈↓∧A, (B C D E)␈↓↓] = ␈↓∧(A B C D E).
␈↓ ↓H␈↓∧␈↓If␈α we␈α want␈α ␈↓αcons␈↓↓[␈↓αx␈↓↓,␈α ␈↓αy␈↓↓]␈↓␈α to␈α be␈α a␈α list,␈α then␈α ␈↓αy␈↓␈α must␈α be␈α a␈α list␈α (possibly␈α the␈α null␈α list␈α ␈↓∧NIL␈↓),␈α and␈α ␈↓αx␈↓
␈↓ ↓H␈↓must␈α
be␈α
a␈α
list␈α
or␈α
an␈α
atom.␈α
In␈α
the␈α
case␈α
of␈α
S-expressions␈α
in␈α
general,␈α
there␈α
is␈α
no␈α
restriction␈α
on␈α the
␈↓ ↓H␈↓arguments of ␈↓αcons␈↓. Usually, we shall write ␈↓αx . y␈↓ instead of ␈↓αcons␈↓↓[␈↓αx␈↓↓, ␈↓αy␈↓↓]␈↓ since this is briefer.
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ I8
␈↓ ↓H␈↓ The␈α
first␈α
predicate␈α
is␈α ␈↓βat␈α
␈↓αx␈↓.␈α
␈↓βat␈α
␈↓αx␈↓␈α is␈α
true␈α
if␈α
the␈α S-expression␈α
␈↓αx␈↓␈α
is␈α
atomic␈α
and␈α false
␈↓ ↓H␈↓otherwise.
␈↓ ↓H␈↓ The␈α∀ second␈α∀ predicate␈α∀ is␈α∃equality␈α∀of␈α∀atomic␈α∀symbols␈α∀written␈α∃␈↓αx␈α∀␈↓βeq␈α∀␈↓αy␈↓.␈α∀Equality␈α∃of␈α∀S-
␈↓ ↓H␈↓expressions␈α∂is␈α∞tested␈α∂by␈α∞a␈α∂ program␈α∞ based␈α∂ on␈α∞␈↓βeq␈↓.␈α∂ Actually␈α∞ ␈↓βeq␈↓␈α∂ does␈α∞a␈α∂bit␈α∞more␈α∂than␈α∞testing
␈↓ ↓H␈↓equality␈α of␈α
atoms.␈α Namely,␈α ␈↓αx␈α
␈↓βeq␈α ␈↓αy␈↓␈α
is␈α true␈α if␈α
and␈α only␈α
if␈α the␈α addresses␈α
of␈α the␈α
first␈α words␈α of␈α
the
␈↓ ↓H␈↓S-expressions␈α ␈↓αx␈↓␈α and␈α ␈↓αy␈↓␈α are␈α equal.␈α Therefore,␈α if␈α ␈↓αx␈α ␈↓βeq␈α ␈↓αy␈↓,␈α then␈α ␈↓αx␈↓␈α and␈α ␈↓αy␈↓␈α are␈α certainly␈α the␈α same
␈↓ ↓H␈↓S-expression␈α since␈α they␈α are␈α represented␈α by␈α
the␈α same␈α structure␈α in␈α memory.␈α The␈α converse␈α
is␈α false
␈↓ ↓H␈↓because␈α there␈α is␈α no␈α guarantee␈α in␈α general␈α that␈α the␈α same␈α S-expression␈α is␈α not␈α represented␈α by␈α two
␈↓ ↓H␈↓different␈α list␈α structures.␈α In␈α the␈α particular␈α case␈α where␈α at␈α least␈α one␈α of␈α the␈α S-expressions␈α is␈α known␈α to
␈↓ ↓H␈↓be an atom, this guarantee can be given, because LISP represents atoms uniquely in memory.
␈↓ ↓H␈↓ The␈α above␈α are␈α all␈α
the␈α basic␈α functions␈α of␈α
LISP;␈α all␈α other␈α LISP␈α
functions␈α can␈α be␈α built␈α
from
␈↓ ↓H␈↓them␈α∞ using␈α∞ recursive␈α
conditional␈α∞expressions␈α∞as␈α
will␈α∞shortly␈α∞be␈α
explained.␈α∞However,␈α∞the␈α∞use␈α
of
␈↓ ↓H␈↓certain abbreviations makes LISP programs easier to write and understand.
␈↓ ↓H␈↓ ␈↓βn␈α
␈↓αx␈↓␈α
is␈α an␈α
abbreviation␈α
for␈α ␈↓αx␈α
␈↓βeq␈α
␈↓∧NIL␈↓.␈α
It␈α rates␈α
a␈α
special␈α notation␈α
because␈α
␈↓∧NIL␈↓␈α
plays␈α the
␈↓ ↓H␈↓same␈α∞ role␈α∞ among␈α∂ lists␈α∞ that␈α∞ zero␈α∞plays␈α∂ among␈α∞ numbers,␈α∞ and␈α∞list␈α∂variables␈α∞often␈α∞have␈α∂to␈α∞be
␈↓ ↓H␈↓tested to see if their value is ␈↓∧NIL␈↓.
␈↓ ↓H␈↓ The␈α notation␈α ␈↓αlist␈↓↓[␈↓αx1,␈α
x2,␈α .␈α .␈α .␈α
,␈α xn␈↓↓]␈↓␈α is␈α
used␈α to␈α denote␈α the␈α
composition␈α of␈α ␈↓αcons␈↓'s␈α that␈α
forms
␈↓ ↓H␈↓a list from its elements. Thus
␈↓ ↓H␈↓ ␈↓αlist␈↓↓[␈↓αx, y, z␈↓↓] = ␈↓αcons␈↓↓[␈↓αx, cons␈↓↓[␈↓αy, cons␈↓↓[␈↓αz, ␈↓∧NIL␈↓↓]]]
␈↓ ↓H␈↓↓␈↓and␈α forms␈α a␈α list␈α of␈α three␈α elements␈α out␈α of␈α the␈α quantities␈α ␈↓αx,␈α y,␈α ␈↓␈α and␈α ␈↓αz␈↓.␈α We␈α often␈α write␈α ␈↓↓<␈↓αx␈α y␈α .␈α .␈α .
␈↓ ↓H␈↓αz␈↓↓>␈↓ instead of ␈↓αlist␈↓↓[␈↓αx, y, . . . , z␈↓↓]␈↓ when this will not cause confusion.
␈↓ ↓H␈↓ Compositions␈α of␈α ␈↓βa␈↓␈α and␈α ␈↓βd␈↓␈α are␈α written␈α by␈α concatenating␈α the␈α letters␈α ␈↓βa␈↓␈α and␈α ␈↓βd␈↓.␈α Thus,␈α it␈α is
␈↓ ↓H␈↓easily␈α∂seen␈α∂that␈α∂ ␈↓βad␈α∂␈↓αx␈↓␈α⊂ denotes␈α∂the␈α∂second␈α∂element␈α∂of␈α∂the␈α⊂list␈α∂ ␈↓αx␈↓,␈α∂and␈α∂ ␈↓βadd␈α∂␈↓αx␈↓␈α∂ denotes␈α⊂the␈α∂third
␈↓ ↓H␈↓element of that list.
␈↓ ↓H␈↓6. ␈↓βConditional expressions.␈↓
␈↓ ↓H␈↓ When␈α the␈α form␈α that␈α represents␈α a␈α function␈α depends␈α on␈α whether␈α a␈α certain␈α predicate␈α is␈α true␈α of
␈↓ ↓H␈↓the arguments, conditional expressions. are used. The conditional expression
␈↓ ↓H␈↓ ␈↓βif ␈↓αp ␈↓βthen ␈↓αa ␈↓βelse ␈↓αb
␈↓ ↓H␈↓α␈↓is␈α∞evaluated␈α
as␈α∞follows:␈α
First␈α∞ ␈↓αp␈↓␈α
is␈α∞evaluated␈α∞and␈α
determined␈α∞to␈α
be␈α∞true␈α
or␈α∞false.␈α
If␈α∞ ␈↓αp␈↓␈α∞ is␈α
true,
␈↓ ↓H␈↓then␈α ␈↓αa␈↓␈α is␈α evaluated␈α and␈α its␈α value␈α is␈α the␈α value␈α of␈α the␈α expression.␈α If␈α ␈↓αp␈↓␈α is␈α false,␈α then␈α ␈↓αb␈↓␈α is
␈↓ ↓H␈↓evaluated␈α∩and␈α⊃its␈α∩value␈α⊃is␈α∩the␈α⊃value␈α∩of␈α∩the␈α⊃expression.␈α∩ Note␈α⊃that␈α∩if␈α⊃␈↓αp␈↓␈α∩ is␈α⊃true,␈α∩ ␈↓αb␈↓␈α∩ is␈α⊃never
␈↓ ↓H␈↓evaluated,␈α and␈α
if␈α ␈↓αp␈↓␈α
is␈α false,␈α
then␈α ␈↓αa␈↓␈α
is␈α never␈α
evaluated.␈α The␈α
importance␈α of␈α
this␈α will␈α be␈α
explained
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ I9
␈↓ ↓H␈↓later.␈α∞ A␈α∞familiar␈α∞ function␈α∂that␈α∞can␈α∞be␈α∞written␈α∂conveniently␈α∞using␈α∞conditional␈α∞expressions␈α∂is␈α∞the
␈↓ ↓H␈↓absolute value of a real number. We have
␈↓ ↓H␈↓ ␈↓↓|␈↓αx␈↓↓| = ␈↓βif ␈↓αx␈↓↓<␈↓∧0 ␈↓βthen ␈↓↓-␈↓αx ␈↓βelse ␈↓αx.
␈↓ ↓H␈↓α␈↓A more general form of conditional expression is
␈↓ ↓H␈↓ ␈↓βif ␈↓αp ␈↓βthen ␈↓αa ␈↓βelse if ␈↓αq ␈↓βthen ␈↓αb . . . ␈↓βelse if ␈↓αs ␈↓βthen ␈↓αd ␈↓βelse ␈↓αe.
␈↓ ↓H␈↓α␈↓There␈α can␈α be␈α any␈α number␈α of␈α terms;␈α the␈α value␈α is␈α determined␈α by␈α evaluating␈α the␈α propositional
␈↓ ↓H␈↓terms␈α ␈↓αp,␈α q␈↓,␈α etc.␈α until␈α a␈α true␈α term␈α is␈α found;␈α the␈α value␈α is␈α then␈α that␈α of␈α the␈α term␈α following␈α the␈α next
␈↓ ↓H␈↓␈↓βthen␈↓.␈α
If␈α
none␈α
of␈α
the␈α
propositional␈α
terms␈α
is␈α
true,␈α
then␈α
the␈α
value␈α
is␈α
that␈α
of␈α
the␈α
term␈α∞following␈α
the
␈↓ ↓H␈↓␈↓βelse␈↓.
␈↓ ↓H␈↓ The function graphed in figure 4 is described by the equation
␈↓ ↓H␈↓ ␈↓αtri␈↓↓[␈↓αx␈↓↓] = ␈↓βif ␈↓αx␈↓↓<-␈↓∧1 ␈↓βthen ␈↓∧0 ␈↓βelse if ␈↓αx␈↓↓<␈↓∧0 ␈↓βthen ␈↓∧1␈↓↓+␈↓αx ␈↓βelse if ␈↓αx␈↓↓<␈↓∧1 ␈↓βthen ␈↓∧1␈↓↓-␈↓αx ␈↓βelse ␈↓∧0.
␈↓"␈↓ ↓H␈↓ ␈αλ ~
␈↓"␈↓ ↓H␈↓ ␈αλ ~
␈↓"␈↓ ↓H␈↓ ≤'`≥(0,1)␈↓ ↓H␈αλ ~
␈↓"␈↓ ↓H␈↓ ≤'␈αλ ~␈αλ `≥
␈↓"␈↓ ↓H␈↓ ≤'␈αλ ~␈αλ `≥
␈↓"␈↓ ↓H␈↓ ≤'␈αλ ~␈αλ `≥
␈↓"␈↓ ↓H␈↓ '␈αλ ~␈αλ `␈↓ ↓H ======================αααααααααααααααααα======================
␈↓"␈↓ ↓H␈↓ ␈αλ (-1,0) ~ (1,0)
␈↓"␈↓ ↓H␈↓ ␈αλ ~
␈↓"␈↓ ↓H␈↓ ␈αλ ~
␈↓"␈↓ ↓H␈↓ Figure 4.
␈↓ ↓H␈↓∧7. ␈↓βBoolean expressions.␈↓
␈↓ ↓H␈↓ In␈α∩ making␈α∩ up␈α∪ the␈α∩ propositional␈α∩ parts␈α∩ of␈α∪ conditional␈α∩expressions,␈α∩ it␈α∪ is␈α∩ often
␈↓ ↓H␈↓necessary␈α∂ to␈α∞ combine␈α∂ elementary␈α∂propositional␈α∞expressions␈α∂using␈α∞the␈α∂Boolean␈α∂operators␈α∞ and,
␈↓ ↓H␈↓or,␈α and␈α
not.␈α We␈α
use␈α the␈α symbols␈α
␈↓↓∧␈↓,␈α ␈↓↓∨␈↓,␈α
and␈α ␈↓↓¬␈↓␈α respectively,␈α
for␈α these␈α
operators.␈α In␈α LISP,␈α
the
␈↓ ↓H␈↓atoms␈α∂ ␈↓∧T␈↓␈α∂ and␈α∂ ␈↓∧NIL␈↓␈α∂ are␈α∂used␈α∂for␈α⊂ the␈α∂ truth␈α∂values.␈α∂ The␈α∂Boolean␈α∂operators␈α∂may␈α⊂be␈α∂described
␈↓ ↓H␈↓simply␈α∀by␈α∪listing␈α∀the␈α∀values␈α∪of␈α∀the␈α∀elementary␈α∪Boolean␈α∀expressions␈α∀for␈α∪ each␈α∀ case␈α∀ of␈α∪ the
␈↓ ↓H␈↓arguments. Thus we have:
␈↓ ↓H␈↓ ␈↓∧T␈↓↓∧␈↓∧T ␈↓↓= ␈↓∧T
␈↓ ↓H␈↓∧␈↓ ␈↓∧T␈↓↓∧␈↓∧F ␈↓↓= ␈↓∧F
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :10
␈↓ ↓H␈↓∧␈↓ ␈↓∧F␈↓↓∧␈↓∧T ␈↓↓= ␈↓∧F
␈↓ ↓H␈↓∧␈↓ ␈↓∧F␈↓↓∧␈↓∧F ␈↓↓= ␈↓∧F
␈↓ ↓H␈↓∧␈↓ ␈↓∧T␈↓↓∨␈↓∧T ␈↓↓= ␈↓∧T
␈↓ ↓H␈↓∧␈↓ ␈↓∧T␈↓↓∨␈↓∧F ␈↓↓= ␈↓∧T
␈↓ ↓H␈↓∧␈↓ ␈↓∧F␈↓↓∨␈↓∧T ␈↓↓= ␈↓∧T
␈↓ ↓H␈↓∧␈↓ ␈↓∧F␈↓↓∨␈↓∧F ␈↓↓= ␈↓∧F
␈↓ ↓H␈↓∧␈↓ ␈↓∧␈↓↓¬␈↓∧T ␈↓↓= ␈↓∧F
␈↓ ↓H␈↓∧␈↓ ␈↓∧␈↓↓¬␈↓∧F ␈↓↓= ␈↓∧T.
␈↓ ↓H␈↓∧␈↓ ␈↓∧␈↓The␈α∞ Boolean␈α∂ operators␈α∞ can␈α∞ be␈α∂ described␈α∞ by␈α∞ conditional␈α∂expressions␈α∞in␈α∂the␈α∞following
␈↓ ↓H␈↓way:
␈↓ ↓H␈↓ ␈↓αp␈↓↓∧␈↓αq ␈↓↓= ␈↓βif ␈↓αp ␈↓βthen ␈↓αq ␈↓βelse ␈↓∧F
␈↓ ↓H␈↓∧␈↓ ␈↓∧␈↓αp␈↓↓∨␈↓αq ␈↓↓= ␈↓βif ␈↓αp ␈↓βthen ␈↓∧T ␈↓βelse ␈↓αq
␈↓ ↓H␈↓α␈↓ ␈↓α␈↓↓¬␈↓αp ␈↓↓= ␈↓βif ␈↓αp ␈↓βthen ␈↓∧F ␈↓βelse ␈↓∧T.
␈↓ ↓H␈↓∧␈↓Note␈α that␈α if␈α ␈↓αp␈↓␈α is␈α false␈α ␈↓αp␈↓↓∧␈↓αq␈↓␈α is␈α false␈α independent␈α of␈α the␈α value␈α of␈α ␈↓αq␈↓,␈α and␈α likewise␈α if␈α ␈↓αp␈↓␈α is␈α true,
␈↓ ↓H␈↓then␈α∞ ␈↓αp␈↓↓∨␈↓αq␈↓␈α∂ is␈α∞true␈α∞independent␈α∂of␈α∞␈↓αq␈↓.␈α∂ If␈α∞ ␈↓αp␈↓␈α∞ has␈α∂been␈α∞evaluated␈α∂and␈α∞found␈α∞to␈α∂be␈α∞false,␈α∂then␈α∞ ␈↓αq␈↓
␈↓ ↓H␈↓does␈α∂not␈α∂ have␈α⊂ to␈α∂ be␈α∂evaluated␈α⊂at␈α∂all␈α∂to␈α⊂find␈α∂the␈α∂value␈α⊂of␈α∂ ␈↓αp␈↓↓∧␈↓αq␈↓,␈α∂and,␈α⊂in␈α∂fact,␈α∂LISP␈α⊂does␈α∂not
␈↓ ↓H␈↓evaluate␈α
␈↓αq␈↓␈α
in␈α this␈α
case.␈α
Similarly,␈α ␈↓αq␈↓␈α
is␈α
not␈α
evaluated␈α in␈α
evaluating␈α
␈↓αp␈↓↓∨␈↓αq␈↓␈α if␈α
␈↓αp␈↓␈α
is␈α
true.␈α This
␈↓ ↓H␈↓procedure␈α⊂is␈α⊃in␈α⊂accordance␈α⊃with␈α⊂the␈α⊂above␈α⊃conditional␈α⊂expression␈α⊃descriptions␈α⊂of␈α⊃ the␈α⊂Boolean
␈↓ ↓H␈↓operators.␈α The␈α importance␈α of␈α
this␈α convention␈α which␈α contrasts␈α with␈α
that␈α of␈α ALGOL␈α 60,␈α
will␈α be
␈↓ ↓H␈↓apparent later when we discuss recursive definitions of functions and predicates.
␈↓ ↓H␈↓8. ␈↓βRecursive function definitions.␈↓
␈↓ ↓H␈↓ In␈α∞such␈α
languages␈α∞as␈α
FORTRAN␈α∞and␈α
Algol,␈α∞ computer␈α
progrrams␈α∞are␈α
expressed␈α∞ in␈α
the
␈↓ ↓H␈↓main␈α as␈α sequences␈α of␈α assignment␈α statements␈α and␈α conditional␈α go␈α to's.␈α In␈α LISP,␈α programs␈α are␈α mainly
␈↓ ↓H␈↓expressed in the form of recursively defined functions. We begin with an example.
␈↓ ↓H␈↓ The␈α∞ function␈α∞ ␈↓αalt␈↓↓[␈↓αx␈↓↓]␈↓␈α∞ gives␈α∞ a␈α∞ list␈α∂ whose␈α∞ elements␈α∞ are␈α∞alternate␈α∞elements␈α∞of␈α∞the␈α∂list␈α∞ ␈↓αx␈↓
␈↓ ↓H␈↓beginning with the first. Thus
␈↓ ↓H␈↓ ␈↓αalt␈↓↓[␈↓∧(A B C D E)␈↓↓] = ␈↓∧(A C E),
␈↓ ↓H␈↓∧␈↓ ␈↓∧␈↓αalt␈↓↓[␈↓∧(((A B) (C D))␈↓↓] = ␈↓∧((A B)),
␈↓ ↓H␈↓∧␈↓ ␈↓∧␈↓αalt␈↓↓[␈↓∧(A)␈↓↓] = ␈↓∧(A),
␈↓ ↓H␈↓∧␈↓and
␈↓ ↓H␈↓ ␈↓αalt␈↓↓[␈↓∧NIL␈↓↓] = ␈↓∧NIL.
␈↓ ↓H␈↓∧␈↓ ␈↓∧The function ␈↓αalt␈↓ is defined by the equation
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :11
␈↓ ↓H␈↓ alt␈↓↓[␈↓αx␈↓↓] ← ␈↓βif n ␈↓αx ␈↓↓∨ ␈↓βn d ␈↓αx ␈↓βthen ␈↓αx ␈↓βelse a ␈↓αx . alt␈↓↓[␈↓βdd ␈↓αx␈↓↓].
␈↓ ↓H␈↓↓␈↓ ␈↓↓␈↓The␈α
above␈α
definition␈α is␈α
best␈α
explained␈α by␈α
using␈α
it␈α to␈α
evaluate␈α
some␈α
expressions.␈α We
␈↓ ↓H␈↓start␈α with␈α ␈↓αalt␈↓↓[␈↓∧NIL␈↓↓]␈↓.␈α To␈α evaluate␈α this␈α expression␈α we␈α evaluate␈α the␈α expression␈α to␈α the␈α right␈α of␈α the␈α
␈↓↓←␈↓
␈↓ ↓H␈↓sign␈α
remembering␈α
that␈α
the␈α
variable␈α
␈↓αx␈↓␈α
has␈α
the␈α
value␈α
␈↓∧NIL␈↓.␈α
A␈α
conditional␈α
expression␈α is␈α
evaluated
␈↓ ↓H␈↓by␈α
first␈α
evaluating␈α
the␈α
first␈α
propositional␈α∞term␈α
¬␈α
in␈α
this␈α
case␈α
␈↓βn␈α
␈↓αx␈α∞␈↓↓∨␈α
␈↓βn␈α
d␈α
␈↓αx␈↓.␈α
This␈α
expression␈α∞is␈α
a
␈↓ ↓H␈↓disjunction␈α and␈α in␈α its␈α evaluation␈α we␈α first␈α evaluate␈α the␈α first␈α disjunct,␈α namely␈α ␈↓βn ␈↓αx␈↓.␈α Since␈α ␈↓αx␈α ␈↓↓=␈α ␈↓∧NIL,
␈↓ ↓H␈↓∧␈↓βn␈α ␈↓αx␈↓␈α is␈α true,␈α the␈α disjunction␈α is␈α true,␈α and␈α the␈α value␈α of␈α the␈α conditional␈α expression␈α is␈α the␈α value␈α of
␈↓ ↓H␈↓the␈α∞term␈α
after␈α∞the␈α
first␈α∞true␈α
propositiional␈α∞term.␈α∞The␈α
term␈α∞is␈α
␈↓αx␈↓,␈α∞ and␈α
its␈α∞ value␈α
is␈α∞␈↓∧NIL␈↓,␈α∞ so␈α
the
␈↓ ↓H␈↓value␈α
of␈α
␈↓αalt␈↓↓[␈↓∧NIL␈↓↓]␈↓␈α∞ is␈α
␈↓∧NIL␈↓␈α
as␈α
stated␈α∞above.␈α
Obeying␈α
the␈α
rules␈α∞about␈α
the␈α
order␈α
of␈α∞evaluation␈α
of
␈↓ ↓H␈↓terms␈α∞in␈α∂ conditional␈α∞ and␈α∂Boolean␈α∞expressions␈α∂is␈α∞important␈α∂in␈α∞this␈α∂case␈α∞since␈α∂if␈α∞we␈α∂didn't␈α∞obey
␈↓ ↓H␈↓these␈α rules,␈α we␈α might␈α find␈α ourselves␈α trying␈α to␈α evaluate␈α ␈↓βn␈α d␈α ␈↓αx␈↓␈α or␈α ␈↓αalt␈↓↓[␈↓βdd␈α ␈↓αx␈↓↓]␈↓,␈α and␈α since␈α ␈↓αx␈↓␈α
is␈α ␈↓∧NIL␈↓,
␈↓ ↓H␈↓neither␈α∞of␈α∞these␈α
has␈α∞a␈α∞value.␈α∞ An␈α
attempt␈α∞to␈α∞evaluate␈α
them␈α∞in␈α∞LISP␈α∞would␈α
give␈α∞rise␈α∞to␈α∞an␈α
error
␈↓ ↓H␈↓return.
␈↓ ↓H␈↓ As␈α
a␈α second␈α
example,␈α consider␈α
␈↓αalt␈↓↓[␈↓∧(A␈α
B)␈↓↓]␈↓.␈α Since␈α
neither␈α ␈↓βn␈α
␈↓αx␈↓␈α nor␈α
␈↓βn␈α
d␈α ␈↓αx␈↓␈α
is␈α true␈α
in␈α this␈α
case,
␈↓ ↓H␈↓the␈α disjunction␈α ␈↓βn␈α ␈↓αx␈α ␈↓↓∨␈α ␈↓βn␈α d␈α ␈↓αx␈α ␈↓is␈α false␈α and␈α the␈α value␈α of␈α the␈α expression␈α is␈α the␈α value␈α of␈α ␈↓βa␈α ␈↓αx␈α .
␈↓ ↓H␈↓αalt␈↓↓[␈↓βdd␈α ␈↓αx␈↓↓].␈α ␈↓βa␈α ␈↓αx␈↓␈α has␈α the␈α value␈α ␈↓∧A␈↓,␈α and␈α ␈↓βdd␈α ␈↓αx␈↓␈α has␈α the␈α value␈α ␈↓∧NIL␈↓,␈α so␈α we␈α must␈α now␈α evaluate␈α ␈↓αalt␈↓↓[␈↓∧NIL␈↓↓]␈↓,
␈↓ ↓H␈↓and␈α∞we␈α∞already␈α∞know␈α∞that␈α
the␈α∞value␈α∞ of␈α∞ this␈α∞ expression␈α
is␈α∞ ␈↓∧NIL␈↓.␈α∞ Therefore,␈α∞ the␈α∞ value␈α
of
␈↓ ↓H␈↓␈↓αalt␈↓↓[␈↓∧(A B)␈↓↓]␈↓ is that of ␈↓∧A.NIL␈↓ which is ␈↓∧(A)␈↓.
␈↓ ↓H␈↓ We can describe this evaluation in a less wordy way by writing
␈↓ ↓H␈↓ ␈↓αalt␈↓↓[␈↓∧(A B)␈↓↓] = ␈↓βif n␈↓∧(A B) ␈↓↓∨ ␈↓βn d␈↓∧(A B) ␈↓βthen ␈↓∧(A B) ␈↓βelse
␈↓ ↓H␈↓β a␈↓∧(A B).␈↓αalt␈↓↓[␈↓βdd␈↓∧(A B)␈↓↓]
␈↓ ↓H␈↓↓ = ␈↓βif ␈↓∧NIL ␈↓↓∨ ␈↓βn d␈↓∧(A B) ␈↓βthen ␈↓∧(A B) ␈↓βelse
␈↓ ↓H␈↓β a␈↓∧(A B).␈↓αalt␈↓↓[␈↓βdd␈↓∧(A B)␈↓↓]
␈↓ ↓H␈↓↓ = ␈↓βif ␈↓∧NIL ␈↓βthen ␈↓∧(A B) ␈↓βelse
␈↓ ↓H␈↓β a␈↓∧(A B).␈↓αalt␈↓↓[␈↓βdd␈↓∧(A B)␈↓↓]
␈↓ ↓H␈↓↓ = ␈↓βa␈↓∧(A B).␈↓αalt␈↓↓[␈↓βdd␈↓∧(A B)␈↓↓]
␈↓ ↓H␈↓↓ = ␈↓∧A.␈↓αalt␈↓↓[␈↓∧NIL␈↓↓]
␈↓ ↓H␈↓↓ = ␈↓∧A␈↓↓.[␈↓βif n␈↓∧NIL ␈↓↓∨ ␈↓βnd␈↓∧NIL ␈↓βthen ␈↓∧NIL ␈↓βelse
␈↓ ↓H␈↓β a␈↓∧NIL.␈↓αalt␈↓↓[␈↓βdd␈↓∧NIL␈↓↓]]
␈↓ ↓H␈↓↓ = ␈↓∧A␈↓↓.[␈↓βif ␈↓∧T ␈↓↓∨ ␈↓βnd␈↓∧NIL ␈↓βthen ␈↓∧NIL ␈↓βelse
␈↓ ↓H␈↓β a␈↓∧NIL.␈↓αalt␈↓↓[␈↓βdd␈↓∧NIL␈↓↓]]
␈↓ ↓H␈↓↓ = ␈↓∧A␈↓↓.[␈↓βif ␈↓∧T ␈↓βthen ␈↓∧NIL ␈↓βelse
␈↓ ↓H␈↓β a␈↓∧NIL.␈↓αalt␈↓↓[␈↓βdd␈↓∧NIL␈↓↓]]
␈↓ ↓H␈↓↓ = ␈↓∧A␈↓↓.[␈↓∧NIL␈↓↓]
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :12
␈↓ ↓H␈↓↓ = ␈↓∧(A).
␈↓ ↓H␈↓∧␈↓ ␈↓∧␈↓This␈α⊂is␈α⊃still␈α⊂very␈α⊃ long-winded,␈α⊂ and␈α⊃ now␈α⊂ that␈α⊃ the␈α⊂ reader␈α⊃understands␈α⊂ the␈α⊃ order␈α⊂ of
␈↓ ↓H␈↓evaluation of conditional and Boolean expressions, we can proceed more briefly to evaluate
␈↓ ↓H␈↓ ␈↓αalt␈↓↓[␈↓∧(A B C D E)␈↓↓] = ␈↓∧A.␈↓αalt␈↓↓[␈↓∧(C D E)␈↓↓]
␈↓ ↓H␈↓↓ = ␈↓∧A␈↓↓.[␈↓∧C.␈↓αalt␈↓↓[␈↓∧(E)␈↓↓]]
␈↓ ↓H␈↓↓ = ␈↓∧A.␈↓↓[␈↓∧C.(E)␈↓↓]
␈↓ ↓H␈↓↓ = ␈↓∧(A C E).
␈↓ ↓H␈↓∧␈↓ ␈↓∧␈↓Here␈α
are␈α
three␈α
more␈α
examples␈α
of␈α recursive␈α
functions␈α
and␈α
their␈α
application:␈α
We␈α
define␈α ␈↓αlast␈↓
␈↓ ↓H␈↓by
␈↓ ↓H␈↓ ␈↓αlast␈↓↓[␈↓αx␈↓↓] ← ␈↓βif n d ␈↓αx ␈↓βthen a ␈↓αx ␈↓βelse ␈↓αlast␈↓↓[␈↓βd ␈↓αx␈↓↓],
␈↓ ↓H␈↓↓␈↓and we compute
␈↓ ↓H␈↓ ␈↓αlast␈↓↓[␈↓∧(A B C)␈↓↓] = ␈↓βif nd␈↓∧(A B C) ␈↓βthen a␈↓∧(A B C) ␈↓βelse ␈↓αlast␈↓↓[␈↓βd␈↓∧(A B C)␈↓↓]
␈↓ ↓H␈↓↓ = ␈↓αlast␈↓↓[␈↓∧(B C)␈↓↓]
␈↓ ↓H␈↓↓ = ␈↓αlast␈↓↓[␈↓∧(C)␈↓↓]
␈↓ ↓H␈↓↓ = ␈↓∧C.
␈↓ ↓H␈↓∧␈↓Clearly␈α
␈↓αlast␈↓␈α
computes␈α the␈α
last␈α
element␈α of␈α
a␈α
list.␈α ␈↓αlast␈↓↓[␈↓∧NIL␈↓↓]␈↓␈α
is␈α
undefined␈α in␈α
the␈α
LISP␈α language;
␈↓ ↓H␈↓the␈α⊃result␈α⊂of␈α⊃trying␈α⊂ to␈α⊃ compute␈α⊂ it␈α⊃may␈α⊂be␈α⊃an␈α⊂error␈α⊃message␈α⊂or␈α⊃may␈α⊂be␈α⊃some␈α⊃random␈α⊂result
␈↓ ↓H␈↓depending on the implementation.
␈↓ ↓H␈↓ The function ␈↓αsubst␈↓ is defined by
␈↓ ↓H␈↓ ␈↓αsubst␈↓↓[␈↓αx, y, z␈↓↓] ← ␈↓βif at ␈↓αz ␈↓βthen ␈↓↓[␈↓βif ␈↓αz ␈↓βeq ␈↓αy ␈↓βthen ␈↓αx ␈↓βelse ␈↓αz␈↓↓]
␈↓ ↓H␈↓↓ ␈↓βelse ␈↓αsubst␈↓↓[␈↓αx, y, ␈↓βa ␈↓αz␈↓↓].␈↓αsubst␈↓↓[␈↓αx, y, ␈↓βd ␈↓αz␈↓↓].
␈↓ ↓H␈↓↓␈↓We have
␈↓ ↓H␈↓ ␈↓αsubst␈↓↓[␈↓∧(A.B), X, ((X.A).X)␈↓↓] =
␈↓ ↓H␈↓↓␈↓ ␈↓↓= ␈↓αsubst␈↓↓[␈↓∧(A.B), X, (X.A)␈↓↓]␈↓αsubst␈↓↓[␈↓∧(A.B), X, X␈↓↓]
␈↓ ↓H␈↓↓␈↓ ␈↓↓= [␈↓αsubst␈↓↓[␈↓∧(A.B), X, X␈↓↓].␈↓αsubst␈↓↓[␈↓∧(A.B), X, A␈↓↓]].␈↓∧(A.B)
␈↓ ↓H␈↓∧␈↓ ␈↓∧␈↓↓= [[␈↓∧(A.B)␈↓↓].␈↓∧A␈↓↓].␈↓∧(A.B)␈↓↓]
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :13
␈↓ ↓H␈↓↓␈↓ ␈↓↓= ␈↓∧(((A.B).A).(A.B)).
␈↓ ↓H␈↓∧␈↓αsubst␈↓␈α
computes␈α
the␈α
result␈α
of␈α
substituting␈α
the␈α S-expression␈α
␈↓αx␈↓␈α
for␈α
the␈α
atom␈α
␈↓αy␈↓␈α
in␈α the␈α
S-expression
␈↓ ↓H␈↓␈↓αz␈↓. This is an important operation in all kinds of symbolic computation.
␈↓ ↓H␈↓ Another␈α
important␈α
operation␈α
is␈α
the␈α
concatenation␈α
of␈α
lists,␈α
and␈α
it␈α
is␈α
generally␈α∞denoted␈α
by
␈↓ ↓H␈↓the infixed expression ␈↓αx␈↓↓*␈↓αy␈↓ since it is associative. We have the examples
␈↓ ↓H␈↓ ␈↓∧(A B C)␈↓↓*␈↓∧(D E F) ␈↓↓= ␈↓∧(A B C D E F),
␈↓ ↓H␈↓∧␈↓and
␈↓ ↓H␈↓ ␈↓∧NIL␈↓↓*␈↓∧(A B) ␈↓↓= ␈↓∧(A B) ␈↓↓= ␈↓∧(A B)␈↓↓*␈↓∧NIL,
␈↓ ↓H␈↓∧␈↓and the formal definition
␈↓ ↓H␈↓ ␈↓αx␈↓↓*␈↓αy ␈↓↓← ␈↓βif n ␈↓αx ␈↓βthen ␈↓αy ␈↓βelse ␈↓↓[␈↓βa ␈↓αx␈↓↓].[[␈↓βd ␈↓αx␈↓↓]*␈↓αy␈↓↓].
␈↓ ↓H␈↓↓␈↓ ␈↓↓␈↓The␈α∂ Boolean␈α∂ operations␈α∂can␈α∞also␈α∂be␈α∂used␈α∂in␈α∞making␈α∂recursive␈α∂definitions␈α∂ provided␈α∞ we
␈↓ ↓H␈↓observe the order of evaluation of constituents. First, we define a predicate ␈↓αequal␈↓ by
␈↓ ↓H␈↓ ␈↓αequal␈↓↓[␈↓αx, y␈↓↓] ← ␈↓αx ␈↓βeq ␈↓αy ␈↓↓∨ [¬␈↓βat ␈↓αx ␈↓↓∧ ¬␈↓βat ␈↓αy ␈↓↓∧
␈↓ ↓H␈↓↓ ␈↓αequal␈↓↓[␈↓βa ␈↓αx, ␈↓βa ␈↓αy␈↓↓] ∧ ␈↓αequal␈↓↓[␈↓βd ␈↓αx, ␈↓βd ␈↓αy␈↓↓]].
␈↓ ↓H␈↓↓␈↓αequal␈↓↓[␈↓αx,␈α
y␈↓↓]␈↓␈α
is␈α
true␈α
if␈α
and␈α only␈α
if␈α
␈↓αx␈↓␈α
and␈α
␈↓αy␈↓␈α
are␈α the␈α
same␈α
S-expression,␈α
and␈α
the␈α
use␈α of
␈↓ ↓H␈↓this␈α
predicate␈α
makes␈α
up␈α
for␈α∞the␈α
fact␈α
that␈α
the␈α
basic␈α∞predicate␈α
␈↓βeq␈↓␈α
is␈α
guaranteed␈α
to␈α∞ test␈α
equality
␈↓ ↓H␈↓only when one of the operands is known to be an atom. We shall also use the infixes ␈↓↓=␈↓ and ␈↓↓≠␈↓.
␈↓ ↓H␈↓ Membership of an S-expression ␈↓αx␈↓ in a list ␈↓αy␈↓ is tested by
␈↓ ↓H␈↓ ␈↓αmember␈↓↓[␈↓αx, y␈↓↓] ← ¬␈↓βn ␈↓αy ␈↓↓∧ [[␈↓αx ␈↓↓= ␈↓βa ␈↓αy␈↓↓] ∨ ␈↓αmember␈↓↓[␈↓αx, ␈↓βd ␈↓αy␈↓↓]].
␈↓ ↓H␈↓↓␈↓This relation is also denoted by ␈↓αx␈↓↓ε␈↓αy. Here are some computations:
␈↓ ↓H␈↓α␈↓ ␈↓αmember␈↓↓[␈↓∧B, (A B)␈↓↓] = ¬␈↓βn ␈↓∧(A B) ␈↓↓∧ [[␈↓∧B ␈↓↓= ␈↓βa ␈↓∧(A B)␈↓↓]
␈↓ ↓H␈↓↓ ∨ ␈↓αmember␈↓↓[␈↓∧B, ␈↓βd ␈↓∧(A B)␈↓↓]],
␈↓ ↓H␈↓↓ = ␈↓αmember␈↓↓[␈↓∧B, (B)␈↓↓]
␈↓ ↓H␈↓↓ = ␈↓∧T.
␈↓ ↓H␈↓∧␈↓ ␈↓∧␈↓Sometimes␈α a␈α function␈α is␈α
defined␈α with␈α the␈α help␈α of␈α
auxiliary␈α functions.␈α Thus,␈α the␈α reverse␈α
of
␈↓ ↓H␈↓a list ␈↓αx␈↓ , (e.g. ␈↓αreverse␈↓↓[␈↓∧(A B C D)␈↓↓] = ␈↓∧(D C B A)␈↓), is given by
␈↓ ↓H␈↓ ␈↓αreverse␈↓↓[␈↓αx␈↓↓] ← ␈↓αrev␈↓↓[␈↓αx, ␈↓∧NIL␈↓↓]
␈↓ ↓H␈↓↓␈↓where
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :14
␈↓ ↓H␈↓ ␈↓αrev␈↓↓[␈↓αx, y␈↓↓] ← ␈↓βif n ␈↓αx ␈↓βthen ␈↓αy ␈↓βelse ␈↓αrev␈↓↓[␈↓βd ␈↓αx␈↓↓, [␈↓βa ␈↓αx␈↓↓].␈↓αy␈↓↓].
␈↓ ↓H␈↓↓␈↓A computation is
␈↓ ↓H␈↓ ␈↓αreverse␈↓↓[␈↓∧(A B C)␈↓↓] = ␈↓αrev␈↓↓[␈↓∧(A B C), NIL␈↓↓]
␈↓ ↓H␈↓↓ = ␈↓αrev␈↓↓[␈↓∧(B C), (A)␈↓↓]
␈↓ ↓H␈↓↓ = ␈↓αrev␈↓↓[␈↓∧(C), (B A)␈↓↓]
␈↓ ↓H␈↓↓ = ␈↓αrev␈↓↓[␈↓∧NIL, (C B A)␈↓↓]
␈↓ ↓H␈↓↓ = ␈↓∧(C B A).
␈↓ ↓H␈↓∧␈↓ ␈↓∧␈↓A more elaborate example of recursive definition is given by
␈↓ ↓H␈↓ ␈↓αflatten␈↓↓[␈↓αx␈↓↓] ← ␈↓αflat␈↓↓[␈↓αx, ␈↓∧NIL␈↓↓]
␈↓ ↓H␈↓↓␈↓ ␈↓↓␈↓αflat␈↓↓[␈↓αx, y␈↓↓] ← ␈↓βif at ␈↓αx ␈↓βthen ␈↓αx.y
␈↓ ↓H␈↓α ␈↓βelse ␈↓αflat␈↓↓[␈↓βa ␈↓αx, flat␈↓↓[␈↓βd ␈↓αx, y␈↓↓]].
␈↓ ↓H␈↓↓␈↓We have
␈↓ ↓H␈↓ ␈↓αflatten␈↓↓[␈↓∧((A.B).C)␈↓↓] = ␈↓αflat␈↓↓[␈↓∧((A.B).C), NIL␈↓↓]
␈↓ ↓H␈↓↓ = ␈↓αflat␈↓↓[␈↓∧(A.B), ␈↓αflat␈↓↓[␈↓∧C, NIL␈↓↓]]
␈↓ ↓H␈↓↓ = ␈↓αflat␈↓↓[␈↓∧(A.B), (C)␈↓↓]
␈↓ ↓H␈↓↓ = ␈↓αflat␈↓↓[␈↓∧A, ␈↓αflat␈↓↓[␈↓∧B, (C)␈↓↓]]
␈↓ ↓H␈↓↓ = ␈↓αflat␈↓↓[␈↓∧A, (B C)␈↓↓]
␈↓ ↓H␈↓↓ = ␈↓∧(A B C).
␈↓ ↓H␈↓∧␈↓The␈α
reader␈α
will␈α see␈α
that␈α
the␈α value␈α
of␈α
␈↓αflatten␈↓↓[␈↓αx␈↓↓]␈↓␈α is␈α
a␈α
list␈α of␈α
the␈α
atoms␈α of␈α
the␈α
S-expression␈α ␈↓αx␈↓
␈↓ ↓H␈↓from left to write. Thus ␈↓αflatten␈↓↓[␈↓∧((A B) A)␈↓↓] = ␈↓∧(A B NIL A NIL)␈↓.
␈↓ ↓H␈↓ Many␈α⊃ functions␈α⊃ can␈α⊃be␈α⊃conveniently␈α⊃written␈α⊃in␈α⊃more␈α⊃than␈α⊃one␈α⊃way.␈α⊃ For␈α⊃example,␈α⊂the
␈↓ ↓H␈↓function ␈↓αreverse␈↓ mentioned above can be written without an auxiliary function as follows:
␈↓ ↓H␈↓ ␈↓αreverse␈↓↓[␈↓αx␈↓↓] ← ␈↓βif n ␈↓αx ␈↓βthen ␈↓∧NIL ␈↓βelse ␈↓αreverse␈↓↓[␈↓βd ␈↓αx␈↓↓]*␈↓∧<a x>
␈↓ ↓H␈↓∧␈↓but it will be explained later that the earlier definition involves less computation.
␈↓ ↓H␈↓ The␈α∞use␈α∞of␈α∞conditional␈α
expressions␈α∞ for␈α∞ recursive␈α∞ function␈α
definition␈α∞ is␈α∞ not␈α∞ limited␈α
to
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :15
␈↓ ↓H␈↓functions␈α of␈α S-expressions.␈α For␈α example,␈α the␈α factorial␈α function␈α and␈α the␈α Euclidean␈α algorithm␈α for
␈↓ ↓H␈↓the greatest common divisor are expressed as follows:
␈↓ ↓H␈↓ ␈↓αn␈↓↓! ← ␈↓βif ␈↓αn␈↓↓=␈↓∧0 ␈↓βthen ␈↓∧1 ␈↓βelse ␈↓αn␈↓↓(␈↓αn␈↓↓-␈↓∧1␈↓↓)!
␈↓ ↓H␈↓↓␈↓and
␈↓ ↓H␈↓ ␈↓αgcd␈↓↓(␈↓αm, n␈↓↓) ← ␈↓βif ␈↓αm␈↓↓>␈↓αn ␈↓βthen ␈↓αgcd␈↓↓(␈↓αn, m␈↓↓) ␈↓βelse if ␈↓αm␈↓↓=␈↓∧0 ␈↓βthen ␈↓αn
␈↓ ↓H␈↓α ␈↓βelse ␈↓αgcd␈↓↓(␈↓αn mod m, m␈↓↓)
␈↓ ↓H␈↓↓␈↓where␈α
␈↓αn␈α
mod␈α
m␈↓␈α
denotes␈α the␈α
remainder␈α
when␈α
␈↓αn␈↓␈α
is␈α
divided␈α by␈α
␈↓αm␈↓␈α
and␈α
may␈α
itself␈α
be␈α expressed
␈↓ ↓H␈↓recursively by
␈↓ ↓H␈↓ ␈↓αn mod m ␈↓↓← ␈↓βif ␈↓αn␈↓↓<␈↓αm ␈↓βthen ␈↓αn ␈↓βelse ␈↓↓(␈↓αn␈↓↓-␈↓αm␈↓↓) ␈↓αmod m.
␈↓ ↓H␈↓α␈↓ Exercises
␈↓ ↓H␈↓ 1. Consider the function ␈↓αdrop␈↓ defined by
␈↓ ↓H␈↓ ␈↓αdrop␈↓↓[␈↓αx␈↓↓] ← ␈↓βif n ␈↓αx ␈↓βthen ␈↓∧NIL ␈↓βelse ␈↓↓<␈↓βa ␈↓αx␈↓↓>.␈↓αdrop␈↓↓[␈↓βd ␈↓αx␈↓↓].
␈↓ ↓H␈↓↓␈↓Compute (by hand) ␈↓αdrop␈↓↓[␈↓∧(A B C)␈↓↓]␈↓. What does ␈↓αdrop␈↓ do to lists in general?
␈↓ ↓H␈↓ 2. What does the function
␈↓ ↓H␈↓ ␈↓αr2␈↓↓[␈↓αx␈↓↓] ← ␈↓βif n ␈↓αx ␈↓βthen ␈↓∧NIL ␈↓βelse ␈↓αreverse␈↓↓[␈↓βa ␈↓αx␈↓↓].␈↓αr2␈↓↓[␈↓βd ␈↓αx␈↓↓]
␈↓ ↓H␈↓↓␈↓do to lists of lists? How about
␈↓ ↓H␈↓ ␈↓αr3␈↓↓[␈↓αx␈↓↓] ← ␈↓βif at ␈↓αx ␈↓βthen ␈↓αx ␈↓βelse ␈↓αreverse␈↓↓[␈↓αr4␈↓↓[␈↓αx␈↓↓]]
␈↓ ↓H␈↓↓␈↓ ␈↓↓␈↓αr4␈↓↓[␈↓αx␈↓↓] ← ␈↓βif n ␈↓αx ␈↓βthen ␈↓∧NIL ␈↓βelse ␈↓αr3␈↓↓[␈↓βa ␈↓αx␈↓↓].␈↓αr4␈↓↓[␈↓βd ␈↓αx␈↓↓]?
␈↓ ↓H␈↓↓␈↓ ␈↓↓␈↓3. Compare
␈↓ ↓H␈↓ ␈↓αr3'␈↓↓[␈↓αx␈↓↓] ← ␈↓βif at ␈↓αx ␈↓βthen ␈↓αx ␈↓βelse ␈↓αr3'␈↓↓[␈↓βd ␈↓αx␈↓↓]*<␈↓αr3'␈↓↓[␈↓βa ␈↓αx␈↓↓]>
␈↓ ↓H␈↓↓␈↓with the function ␈↓αr3␈↓ of the preceding example.
␈↓ ↓H␈↓ 4. Consider ␈↓αr5␈↓ defined by
␈↓ ↓H␈↓ ␈↓αr5␈↓↓[␈↓αx␈↓↓] ← ␈↓βif n ␈↓αx ␈↓↓∨ ␈↓βn d ␈↓αx ␈↓βthen ␈↓αx
␈↓ ↓H␈↓α␈↓ ␈↓α␈↓βelse ␈↓↓[␈↓βa ␈↓αr5␈↓↓[␈↓βd ␈↓αx␈↓↓]]
␈↓ ↓H␈↓↓ . ␈↓αr5␈↓↓[␈↓βa ␈↓αx . r5␈↓↓[␈↓βd ␈↓αr5␈↓↓[␈↓βd ␈↓αx␈↓↓]]].
␈↓ ↓H␈↓↓␈↓Compute␈α ␈↓αr5␈↓↓[␈↓∧(A␈α B␈α C␈α D)␈↓↓]␈↓.␈α What␈α does␈α ␈↓∧r5␈↓␈α do␈α in␈α general?␈α Needless␈α to␈α say,␈α this␈α is␈α not␈α a␈α good␈α way
␈↓ ↓H␈↓of computing this function even though it involves no auxiliary functions.
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :16
␈↓ ↓H␈↓9. ␈↓βLambda expressions and functions with functions as arguments.␈↓
␈↓ ↓H␈↓ It␈α
is␈α
common␈α
to␈α
use␈α
phrases␈α
like␈α
"the␈α
function␈α
2␈↓αx␈↓↓+␈↓αy␈↓".␈α
This␈α
is␈α
not␈α
a␈α
precise␈α notation␈α
because
␈↓ ↓H␈↓we␈α
cannot␈α say␈α
2␈↓αx␈↓↓+␈↓αy␈↓↓(␈↓∧3,␈α
4␈↓↓)␈↓␈α and␈α
know␈α
whether␈α the␈α
desired␈α
result␈α is␈α
2␈↓
␈␈↓3+4␈α
or␈α 2␈↓
␈␈↓4+3␈α
regarding
␈↓ ↓H␈↓the␈α∞expression␈α∞ as␈α∞a␈α∞function␈α∞of␈α∞two␈α∞variables.␈α∞ Worse␈α∞yet,␈α∞we␈α∞might␈α∞have␈α∞meant␈α∞a␈α∞one-variable
␈↓ ↓H␈↓function of ␈↓αx␈↓ wherein ␈↓αy␈↓ is regarded as a parameter.
␈↓ ↓H␈↓ The␈α∂problem␈α∂ of␈α⊂ giving␈α∂ names␈α∂ to␈α∂ functions␈α⊂ is␈α∂ solved␈α∂ by␈α∂Church's␈α⊂ λ-notation.␈α∂ In
␈↓ ↓H␈↓the␈α∂ above␈α∂ example,␈α∂ we␈α∂ would␈α∂ write␈α∂␈↓↓λ␈↓αx␈α⊂y␈↓↓:␈α∂␈↓∧2␈↓αx␈↓↓+␈↓αy␈↓␈α∂ to␈α∂denote␈α∂ the␈α∂ function␈α∂ of␈α⊂ two␈α∂ variables
␈↓ ↓H␈↓with␈α first␈α argument␈α ␈↓αx␈↓␈α and␈α second␈α argument␈α
␈↓αy␈↓␈α whose␈α value␈α is␈α given␈α by␈α the␈α expression␈α
2␈↓αx␈↓↓+␈↓αy␈↓.
␈↓ ↓H␈↓Thus,
␈↓ ↓H␈↓ ␈↓↓[λ␈↓αx y␈↓↓: ␈↓∧2␈↓αx␈↓↓+␈↓αy␈↓↓][␈↓∧3, 4␈↓↓] = ␈↓∧10␈↓.
␈↓ ↓H␈↓Likewise,␈α∩ ␈↓↓[λ␈↓αy␈α⊃x␈↓↓:␈α∩␈↓∧2␈↓αx␈↓↓+␈↓αy␈↓↓][␈↓∧3,␈α⊃4␈↓↓]␈α∩=␈α⊃␈↓∧11␈↓.␈α∩ Like␈α⊃variables␈α∩of␈α⊃integration␈α∩and␈α⊃the␈α∩bound␈α∩variables␈α⊃of
␈↓ ↓H␈↓quantifiers␈α in␈α
logic,␈α variables␈α
following␈α λ␈α
are␈α bound␈α
or␈α dummy␈α
and␈α the␈α
expression␈α as␈α
a␈α whole
␈↓ ↓H␈↓may␈α
be␈α∞replaced␈α
by␈α
any␈α∞others␈α
provided␈α
the␈α∞replacement␈α
is␈α
done␈α∞consistently␈α
and␈α
does␈α∞not␈α
make
␈↓ ↓H␈↓any␈α∂ variable␈α∞ bound␈α∂ by␈α∂ λ␈α∞ the␈α∂same␈α∂as␈α∞a␈α∂free␈α∂variable␈α∞in␈α∂the␈α∂expression.␈α∞ Thus␈α∂ ␈↓↓λ␈↓αx␈α∂y␈↓↓:␈α∞␈↓∧2␈↓αx␈↓↓+␈↓αy␈↓
␈↓ ↓H␈↓represents␈α the␈α same␈α
function␈α as␈α ␈↓↓λ␈↓αy␈α x␈↓↓:␈α
␈↓∧2␈↓αy␈↓↓+␈↓αx␈↓␈α or␈α ␈↓↓λ␈↓αu␈α v␈↓↓:␈α
␈↓∧2␈↓αu␈↓↓+␈↓αv␈↓␈α ,␈α but␈α in␈α
the␈α function␈α of␈α one␈α
argument
␈↓ ↓H␈↓␈↓↓λ␈↓αx␈↓↓: ␈↓∧2␈↓αx␈↓↓+␈↓αy␈↓ , we cannot replace the variable ␈↓αx␈↓ by ␈↓αy␈↓ , though we could replace it by ␈↓αu␈↓.
␈↓ ↓H␈↓ λ-notation␈α plays␈α two␈α important␈α roles␈α in␈α LISP.␈α First,␈α it␈α allows␈α us␈α to␈α rewrite␈α an␈α expression
␈↓ ↓H␈↓containing␈α two␈α or␈α more␈α occurrences␈α of␈α the␈α same␈α sub-expression␈α in␈α such␈α a␈α way␈α that␈α the␈α expression
␈↓ ↓H␈↓occurs␈α∞only␈α∞once.␈α∞Thus␈α∞ ␈↓↓(␈↓∧2␈↓αx␈↓↓+␈↓∧1␈↓↓)↑␈↓∧4␈↓↓+␈↓∧3␈↓↓(␈↓∧2␈↓αx␈↓↓+␈↓∧1␈↓↓)↑␈↓∧3␈↓␈α∞ can␈α∞be␈α∞written␈α∞␈↓↓[λ␈↓αw␈↓↓:␈α∞␈↓αw␈↓↓↑␈↓∧4␈↓↓+␈↓∧3␈↓αw␈↓↓↑␈↓∧3␈↓↓][␈↓∧2␈↓αx␈↓↓+␈↓∧1␈↓↓]␈↓.␈α∞This␈α∂can␈α∞save
␈↓ ↓H␈↓considerable␈α computation,␈α
and␈α corresponds␈α
to␈α the␈α practice␈α
in␈α ordinary␈α
programming␈α of␈α assigning␈α
to
␈↓ ↓H␈↓a␈α variable␈α the␈α value␈α of␈α a␈α sub-expression␈α that␈α occurs␈α more␈α than␈α once␈α in␈α an␈α expression␈α and␈α then
␈↓ ↓H␈↓writing the expression in terms of the variable.
␈↓ ↓H␈↓ The␈α∂second␈α∞use␈α∂of␈α∞λ-expressions␈α∂is␈α∞in␈α∂ using␈α∞ functions␈α∂ that␈α∞take␈α∂functions␈α∂as␈α∞arguments.
␈↓ ↓H␈↓Suppose␈α we␈α
want␈α to␈α form␈α
a␈α new␈α list␈α
from␈α an␈α old␈α
one␈α by␈α applying␈α
a␈α function␈α ␈↓αf␈↓␈α
to␈α each␈α element␈α
of
␈↓ ↓H␈↓the list. This can be done using the function ␈↓αmapcar␈↓ defined by
␈↓ ↓H␈↓ ␈↓αmapcar␈↓↓[␈↓αx, f␈↓↓] ← ␈↓βif n ␈↓αx ␈↓βthen ␈↓∧NIL ␈↓βelse ␈↓αf␈↓↓[␈↓βa ␈↓αx␈↓↓] . ␈↓αmapcar␈↓↓[␈↓βd ␈↓αx, f␈↓↓].
␈↓ ↓H␈↓↓␈↓Suppose␈α
the␈α operation␈α
we␈α want␈α
to␈α perform␈α
is␈α
squaring,␈α and␈α
we␈α want␈α
to␈α apply␈α
it␈α
to␈α the␈α
list␈α ␈↓∧(1␈α
2␈α 3␈α
4
␈↓ ↓H␈↓∧5 6 7)␈↓. We have
␈↓ ↓H␈↓ ␈↓αmapcar␈↓↓[␈↓∧(1 2 3 4 5 6 7), ␈↓↓λ␈↓αx␈↓↓: ␈↓αx␈↓↓↑␈↓∧2␈↓↓] = ␈↓∧(1 4 9 16 25 36 49).
␈↓ ↓H␈↓∧␈↓ ␈↓∧␈↓A␈α
more␈α
generally␈α
useful␈α
operation␈α
than␈α
␈↓αmapcar␈↓␈α
is␈α
␈↓αmaplist␈↓␈α
in␈α
which␈α
the␈α
function␈α
is␈α
applied
␈↓ ↓H␈↓to the successive sublists of the list rather than to the elements. ␈↓αmaplist␈↓ is defined by
␈↓ ↓H␈↓ ␈↓αmaplist␈↓↓[␈↓αx, f␈↓↓] ← ␈↓βif n ␈↓αx ␈↓βthen ␈↓∧NIL ␈↓βelse ␈↓αf␈↓↓[␈↓αx␈↓↓] . ␈↓αmaplist␈↓↓[␈↓βd ␈↓αx, f␈↓↓].
␈↓ ↓H␈↓↓␈↓ ␈↓↓␈↓As␈α∞ an␈α∞ application␈α∞ of␈α∞ ␈↓αmaplist␈↓␈α∞and␈α∞functional␈α∞arguments,␈α∞we␈α∞shall␈α∞define␈α∞a␈α∂function␈α∞ for
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :17
␈↓ ↓H␈↓differentiating␈α algebraic␈α expressions␈α involving␈α sums␈α and␈α products.␈α The␈α expressions␈α are␈α built␈α up
␈↓ ↓H␈↓from atoms denoting variables and integer constants according to the syntax
␈↓ ↓H␈↓ <expression> ::= <variable> | <integer> |
␈↓ ↓H␈↓ (PLUS <explist>) | (TIMES <explist>)
␈↓ ↓H␈↓ <explist> ::= <expression> | <expression><explist>
␈↓ ↓H␈↓Here,␈α∂ ␈↓∧PLUS␈↓␈α⊂ followed␈α∂by␈α⊂a␈α∂list␈α⊂of␈α∂arguments␈α⊂denotes␈α∂the␈α⊂sum␈α∂of␈α⊂these␈α∂arguments␈α⊂and␈α∂ ␈↓∧TIMES␈↓
␈↓ ↓H␈↓followed␈α
by␈α a␈α
list␈α
of␈α arguments␈α
denotes␈α
their␈α product.␈α
The␈α
function␈α ␈↓αdiff␈↓↓[␈↓αe,␈α
v␈↓↓]␈↓␈α
gives␈α the␈α
partial
␈↓ ↓H␈↓derivative of the expression ␈↓αe␈↓ with respect to the variable ␈↓αv␈↓. We have
␈↓ ↓H␈↓ ␈↓αdiff␈↓↓[␈↓αe, v␈↓↓] ← ␈↓βif at ␈↓αe ␈↓βthen ␈↓↓[␈↓βif ␈↓αe ␈↓βeq ␈↓αv ␈↓βthen ␈↓∧1 ␈↓βelse ␈↓∧0␈↓↓]
␈↓ ↓H␈↓↓␈↓ ␈↓↓␈↓βelse if a ␈↓αe ␈↓βeq ␈↓∧PLUS ␈↓βthen
␈↓ ↓H␈↓β ␈↓∧PLUS . ␈↓αmapcar␈↓↓[␈↓βd ␈↓αe␈↓↓, λ␈↓αx␈↓↓: ␈↓αdiff␈↓↓[␈↓αx, v␈↓↓]_]
␈↓ ↓H␈↓↓␈↓ ␈↓↓␈↓βelse if a ␈↓αe ␈↓βeq ␈↓∧TIMES ␈↓αthen
␈↓ ↓H␈↓α ␈↓∧PLUS.␈↓αmaplist␈↓↓[␈↓βd ␈↓αe␈↓↓, λ␈↓αx␈↓↓: ␈↓∧TIMES
␈↓ ↓H␈↓∧ . ␈↓αmaplist␈↓↓[␈↓βd ␈↓αe␈↓↓, λ␈↓αy␈↓↓: ␈↓βif ␈↓αx ␈↓βeq ␈↓αy ␈↓βthen
␈↓ ↓H␈↓β ␈↓αdiff␈↓↓[␈↓βa ␈↓αy, v␈↓↓] ␈↓βelse a ␈↓αy␈↓↓]].
␈↓ ↓H␈↓↓␈↓The term that describes the rule for differentiating products corresponds to the rule
␈↓ ↓H␈↓ ␈↓↓∂/∂␈↓αv e␈↓¬i␈↓↓ = [␈↓βif ␈↓αi␈↓↓=␈↓αj ␈↓βthen ␈↓↓∂␈↓αe␈↓¬j␈↓↓/∂␈↓αv ␈↓βelse ␈↓αe␈↓¬j␈↓↓].
␈↓ ↓H␈↓↓and␈α ␈↓αmaplist␈↓␈α has␈α to␈α be␈α used␈α rather␈α
than␈α ␈↓αmapcar␈↓␈α since␈α whether␈α to␈α differentiate␈α in␈α
forming␈α the
␈↓ ↓H␈↓product␈α is␈α determined␈α by␈α equality␈α of␈α the␈α indices␈α ␈↓αi␈↓␈α and␈α ␈↓αj␈↓␈α rather␈α than␈α equality␈α of␈α the␈α terms␈α ␈↓αe␈↓¬i␈↓
␈↓ ↓H␈↓and ␈↓αe␈↓¬j␈↓.
␈↓ ↓H␈↓ Two␈α more␈α useful␈α functions␈α with␈α functions␈α as␈α arguments␈α are␈α the␈α predicates␈α ␈↓αandlis␈↓␈α and␈α ␈↓αorlis␈↓
␈↓ ↓H␈↓defined by the equations
␈↓ ↓H␈↓ ␈↓αandlis␈↓↓[␈↓αu, p␈↓↓] ← ␈↓βn ␈↓αu ␈↓↓∨ [␈↓αp␈↓↓[␈↓βa ␈↓αu␈↓↓] ∧ ␈↓αandlis␈↓↓[␈↓βd ␈↓αu, p␈↓↓]]
␈↓ ↓H␈↓↓␈↓and
␈↓ ↓H␈↓ ␈↓αorlis␈↓↓[␈↓αu, p␈↓↓] ← ¬␈↓βn ␈↓αu ␈↓↓∧ [␈↓αp␈↓↓[␈↓βa ␈↓αu␈↓↓] ∨ ␈↓αorlis␈↓↓[␈↓βd ␈↓αu, p␈↓↓]].
␈↓ ↓H␈↓↓␈↓ Exercises
␈↓ ↓H␈↓ 1.␈α
Compute␈α ␈↓αdiff␈↓↓[␈↓∧(TIMES␈α
X␈α
(PLUS␈α Y␈α
1)␈α 3),␈α
X␈↓↓]␈↓␈α
using␈α the␈α
above␈α
definition␈α of␈α
␈↓αdiff␈↓.␈α Now␈α
do
␈↓ ↓H␈↓you see why algebraic simplification is important?
␈↓ ↓H␈↓ 2. Compute ␈↓αorlis␈↓↓[␈↓∧((A B) (C D) E), ␈↓βat␈↓↓]␈↓.
␈↓ ↓H␈↓␈↓ ¬wCHAPTER I␈↓ :18
␈↓ ↓H␈↓10. ␈↓βLabel.␈↓
␈↓ ↓H␈↓ The␈α
λ␈α mechanism␈α
is␈α
not␈α adequate␈α
for␈α
providing␈α names␈α
for␈α
recursive␈α functions,␈α
because
␈↓ ↓H␈↓in␈α∪this␈α∪case␈α∩there␈α∪has␈α∪to␈α∩be␈α∪a␈α∪way␈α∪of␈α∩referring␈α∪to␈α∪the␈α∩function␈α∪name␈α∪within␈α∪the␈α∩ function.
␈↓ ↓H␈↓Therefore,␈α we␈α use␈α the␈α notation␈α ␈↓βlabel␈↓↓[␈↓αf,␈α e␈↓↓]␈↓␈α to␈α denote␈α the␈α expression␈α ␈↓αe␈↓␈α but␈α where␈α
occurrences␈α of
␈↓ ↓H␈↓␈↓αf␈↓␈α⊃ within␈α⊃ ␈↓αe␈↓␈α⊃ refer␈α⊃ to␈α⊃ the␈α⊃ whole␈α∩ expression.␈α⊃ For␈α⊃example,␈α⊃ suppose␈α⊃we␈α⊃wished␈α⊃to␈α∩define␈α⊃a
␈↓ ↓H␈↓function␈α that␈α
takes␈α alternate␈α elements␈α
of␈α each␈α
element␈α of␈α a␈α
list␈α and␈α
makes␈α a␈α list␈α
of␈α these.␈α Thus,␈α
we
␈↓ ↓H␈↓want
␈↓ ↓H␈↓ ␈↓αglub␈↓↓[␈↓∧((A B C) (A B C D) (X Y Z))␈↓↓] = ␈↓∧((A C) (A C) (X Z)).
␈↓ ↓H␈↓∧␈↓We can make the definition
␈↓ ↓H␈↓ ␈↓αglub␈↓↓[␈↓αx␈↓↓] ← ␈↓αmapcar␈↓↓[␈↓αx, ␈↓βlabel␈↓↓[␈↓αalt␈↓↓, λ␈↓αx␈↓↓: ␈↓βif n ␈↓αx ␈↓↓∨ ␈↓βn d ␈↓αx ␈↓βthen ␈↓αx
␈↓ ↓H␈↓α ␈↓βelse a ␈↓αx . alt␈↓↓[␈↓βdd ␈↓αx␈↓↓]]].
␈↓ ↓H␈↓↓␈↓The␈α identifier␈α
␈↓αalt␈↓␈α in␈α the␈α
above␈α example␈α is␈α
bound␈α by␈α the␈α
label␈α and␈α is␈α
local␈α to␈α that␈α
expression,
␈↓ ↓H␈↓and␈α∞ this␈α∞is␈α∞the␈α∞general␈α∞rule.␈α
The␈α∞label␈α∞ construction␈α∞is␈α∞not␈α∞often␈α
used␈α∞in␈α∞LISP␈α∞since␈α∞it␈α∞is␈α
more
␈↓ ↓H␈↓usual␈α to␈α give␈α functions␈α global␈α definitions.␈α D.␈α M.␈α R.␈α Park␈α pointed␈α out␈α that␈α if␈α we␈α allow␈α variables␈α to
␈↓ ↓H␈↓represent functions and use a suitable λ construction, the use of label could be avoided.
␈↓ ↓H␈↓␈↓ εP␈↓ :19
␈↓ ↓H␈↓β␈↓ ¬rCHAPTER II
␈↓ ↓H␈↓β␈↓ β.HOW TO WRITE RECURSIVE FUNCTION DEFINITIONS
␈↓ ↓H␈↓1. ␈↓βStatic and dynamic ways of programming.␈↓
␈↓ ↓H␈↓ In␈α∪ order␈α∪ to␈α∀ write␈α∪recursive␈α∪function␈α∪definitions,␈α∀one␈α∪must␈α∪think␈α∀about␈α∪programming
␈↓ ↓H␈↓differently␈α
than␈α is␈α
customary␈α when␈α
writing␈α
programs␈α in␈α
languages␈α like␈α
Fortran␈α or␈α
Algol␈α
or␈α in
␈↓ ↓H␈↓machine␈α∀language.␈α∀ In␈α∀these␈α∃languages,␈α∀one␈α∀has␈α∀in␈α∀mind␈α∃the␈α∀state␈α∀of␈α∀the␈α∃ computation␈α∀ as
␈↓ ↓H␈↓represented␈α
by␈α∞ the␈α
values␈α∞of␈α
certain␈α∞variables␈α
or␈α∞locations␈α
in␈α∞the␈α
memory␈α∞of␈α
the␈α∞machine,␈α
and
␈↓ ↓H␈↓then␈α∂ one␈α∂ writes␈α∂ statements␈α∂ or␈α∂ machine␈α∂instructions␈α∞in␈α∂order␈α∂to␈α∂make␈α∂the␈α∂state␈α∂change␈α∂in␈α∞an
␈↓ ↓H␈↓appropriate way.
␈↓ ↓H␈↓ When␈α writing␈α
LISP␈α recursive␈α
functions␈α one␈α
thinks␈α differently.␈α
Namely,␈α one␈α
thinks␈α about␈α
the
␈↓ ↓H␈↓value␈α⊂of␈α⊂the␈α⊃ function,␈α⊂ asks␈α⊂ for␈α⊂ what␈α⊃values␈α⊂ of␈α⊂the␈α⊂arguments␈α⊃the␈α⊂value␈α⊂of␈α⊂the␈α⊃function␈α⊂is
␈↓ ↓H␈↓immediate,␈α∂and,␈α∂given␈α∂ an␈α∂ arbitrary␈α∂ values␈α∂ of␈α∂ the␈α∂ arguments,␈α∂ for␈α∂ what␈α∂ simpler␈α∂arguments
␈↓ ↓H␈↓must␈α
the␈α function␈α
be␈α known␈α
in␈α order␈α
to␈α give␈α
the␈α value␈α
of␈α the␈α
function␈α for␈α
the␈α given␈α
arguments.
␈↓ ↓H␈↓Let␈α us␈α take␈α a␈α numerical␈α example;␈α namely,␈α suppose␈α we␈α want␈α to␈α compute␈α the␈α function␈α ␈↓αn␈↓↓!␈↓.␈α For
␈↓ ↓H␈↓what␈α argument␈α is␈α the␈α value␈α of␈α the␈α function␈α immediate.␈α Clearly,␈α for␈α ␈↓αn␈α ␈↓↓=␈α ␈↓∧0␈α or␈α ␈↓αn␈α ␈↓↓=␈α ␈↓∧1␈↓,␈α the␈α value␈α is
␈↓ ↓H␈↓immediately␈α
seen␈α∞to␈α
be␈α
1.␈α∞ Moreover,␈α
we␈α
can␈α∞get␈α
the␈α
value␈α∞for␈α
an␈α
arbitrary␈α∞ ␈↓αn␈↓␈α
if␈α
we␈α∞know␈α
the
␈↓ ↓H␈↓value␈α∞ for␈α∞␈↓αn␈↓↓-␈↓∧1.␈α∞ Also,␈α∂we␈α∞see␈α∞that␈α∞knowing␈α∞the␈α∂value␈α∞for␈α∞ ␈↓αn␈α∞␈↓↓=␈α∞␈↓∧1␈α∂ is␈α∞redundant,␈α∞since␈α∞it␈α∂can␈α∞be
␈↓ ↓H␈↓∧obtained␈α from␈α the␈α ␈↓αn␈α
␈↓↓=␈α ␈↓∧0␈α case␈α by␈α the␈α
same␈α rule␈α as␈α gets␈α it␈α
for␈α a␈α general␈α ␈↓αn␈↓∧␈α from␈α
the␈α value
␈↓ ↓H␈↓∧for ␈↓αn␈↓↓-␈↓∧1␈↓. All this talk leads to the simple recursive formula:
␈↓ ↓H␈↓ ␈↓αn␈↓↓! ← ␈↓βif ␈↓αn ␈↓↓= ␈↓∧0 ␈↓βthen ␈↓∧1 ␈↓βelse ␈↓αn␈↓↓(␈↓αn␈↓↓-␈↓∧1␈↓↓)!.
␈↓ ↓H␈↓↓␈↓ ␈↓↓␈↓We␈α may␈α regard␈α this␈α as␈α a␈α static␈α way␈α of␈α looking␈α at␈α programming.␈α We␈α ask␈α what␈α simpler␈α cases
␈↓ ↓H␈↓the␈α
general␈α case␈α
of␈α
our␈α function␈α
depends␈α
on␈α rather␈α
than␈α
how␈α we␈α
build␈α
up␈α the␈α
desired␈α
state␈α of
␈↓ ↓H␈↓the␈α computation.␈α
One␈α often␈α
is␈α led␈α
to␈α believe␈α that␈α
static␈α =␈α
bad␈α and␈α
dynamic␈α =␈α
good,␈α but␈α in␈α
this
␈↓ ↓H␈↓case,␈α the␈α
static␈α way␈α is␈α
often␈α better␈α
than␈α the␈α dynamic␈α
way.␈α LISP␈α
offers␈α both,␈α but␈α
since␈α it␈α is␈α
less
␈↓ ↓H␈↓usual, we shall concentrate on the static way for now.
␈↓ ↓H␈↓ Compare␈α∂ the␈α∂ above␈α∂ recursive␈α∂ definition␈α∂with␈α∂the␈α∂following␈α∂obvious␈α∂Algol␈α∂program␈α∞for
␈↓ ↓H␈↓computing ␈↓αn␈↓↓!:
␈↓ ↓H␈↓↓␈↓ ␈↓↓␈↓βinteger procedure ␈↓αfactorial␈↓↓(␈↓αn␈↓↓); ␈↓βinteger ␈↓αs␈↓↓;
␈↓ ↓H␈↓↓␈↓βbegin
␈↓ ↓H␈↓β␈↓ ␈↓β␈↓αs ␈↓↓:= ␈↓∧1␈↓↓;
␈↓ ↓H␈↓↓␈↓αloop␈↓↓: ␈↓βif ␈↓αn ␈↓↓= ␈↓∧0 ␈↓βthen go to ␈↓αdone␈↓↓;
␈↓ ↓H␈↓↓␈↓ ␈↓↓␈↓αs ␈↓↓:= ␈↓αn␈↓↓*␈↓αs␈↓↓;
␈↓ ↓H␈↓↓␈↓ ␈↓↓␈↓αn ␈↓↓:= ␈↓αn␈↓↓-␈↓∧1␈↓↓;
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :20
␈↓ ↓H␈↓↓␈↓ ␈↓↓␈↓βgo to ␈↓αloop␈↓↓;
␈↓ ↓H␈↓↓␈↓αdone␈↓↓: ␈↓αfactorial ␈↓↓:= ␈↓αs␈↓↓;
␈↓ ↓H␈↓↓␈↓βend␈↓↓;
␈↓ ↓H␈↓↓␈↓ ␈↓↓␈↓The␈α⊂ LISP␈α∂program␈α⊂is␈α∂shorter␈α⊂and␈α∂clearer␈α⊂in␈α∂this␈α⊂particularly␈α∂favorable␈α⊂ case.␈α∂ Actually,
␈↓ ↓H␈↓when␈α we␈α discuss␈α
the␈α mechanism␈α of␈α
recursion,␈α it␈α will␈α
turn␈α out␈α that␈α
the␈α LISP␈α program␈α
will␈α be
␈↓ ↓H␈↓inefficient␈α∪in␈α∩using␈α∪the␈α∩pushdown␈α∪mechanism␈α∪unnecessarily␈α∩and␈α∪should␈α∩be␈α∪ replaced␈α∪by␈α∩ the
␈↓ ↓H␈↓following␈α∃ somewhat␈α∃ longer␈α∀ program␈α∃that␈α∃corresponds␈α∃to␈α∀the␈α∃above␈α∃Algol␈α∃program␈α∀rather
␈↓ ↓H␈↓precisely:
␈↓ ↓H␈↓ ␈↓αn␈↓↓! ← ␈↓αfact␈↓↓(␈↓αn␈↓↓, ␈↓αs␈↓↓),
␈↓ ↓H␈↓↓␈↓where
␈↓ ↓H␈↓ ␈↓αfact␈↓↓(␈↓αn␈↓↓, ␈↓αs␈↓↓) ← ␈↓βif ␈↓αn ␈↓↓= ␈↓∧0 ␈↓βthen ␈↓αs ␈↓βelse ␈↓αfact␈↓↓(␈↓αn␈↓↓-␈↓∧1␈↓↓, ␈↓αn␈↓↓*␈↓αs␈↓↓).
␈↓ ↓H␈↓↓␈↓In fact, compilers should produce the same object code from the two programs.
␈↓ ↓H␈↓2. ␈↓βSimple list recursion.␈↓
␈↓ ↓H␈↓ About␈α
the␈α
simplest␈α
form␈α
of␈α
recursion␈α
in␈α
LISP␈α occurs␈α
when␈α
one␈α
of␈α
the␈α
arguments␈α
is␈α
a␈α list,␈α
the
␈↓ ↓H␈↓result␈α is␈α immediate␈α when␈α the␈α argument␈α is␈α null,␈α and␈α otherwise␈α we␈α need␈α only␈α know␈α the␈α result␈α for␈α the
␈↓ ↓H␈↓␈↓βd␈↓-part␈α
of␈α
that␈α argument.␈α
Consider,␈α
for␈α
example,␈α ␈↓αu␈↓↓*␈↓αv␈↓,␈α
the␈α
concatenation␈α
of␈α the␈α
lists␈α
␈↓αu␈↓␈α
and␈α ␈↓αv␈↓.␈α
The
␈↓ ↓H␈↓result␈α
is␈α immediate␈α
for␈α the␈α
case␈α ␈↓βn␈α
␈↓αu␈↓␈α
and␈α otherwise␈α
depends␈α on␈α
the␈α result␈α
for␈α ␈↓βd␈α
␈↓αu␈↓.␈α
Thus,␈α we
␈↓ ↓H␈↓have
␈↓ ↓H␈↓ ␈↓αu␈↓↓*␈↓αv ␈↓↓← ␈↓βif n ␈↓αu ␈↓βthen ␈↓αv ␈↓βelse a ␈↓αu ␈↓↓. [␈↓βd ␈↓αu ␈↓↓* ␈↓αv␈↓↓].
␈↓ ↓H␈↓↓␈↓On␈α∞the␈α∞other␈α∞hand,␈α∞if␈α∞we␈α∞had␈α∞tried␈α∞to␈α∞recur␈α∞on␈α∞ ␈↓αv␈↓␈α∞ rather␈α∞than␈α∞on␈α∞ ␈↓αu␈↓␈α∞we␈α∞would␈α∞not␈α∞have␈α∞been
␈↓ ↓H␈↓successful.␈α The␈α
result␈α would␈α
be␈α immediate␈α
for␈α ␈↓βn␈α ␈↓αv␈↓,␈α
but␈α ␈↓αu␈↓↓*␈↓αv␈↓␈α
cannot␈α be␈α
constructed␈α in␈α
any␈α direct
␈↓ ↓H␈↓way␈α∞from␈α∞ ␈↓αu␈↓↓*␈↓βd␈α∞␈↓αv␈↓␈α∞without␈α∞ a␈α∞ function␈α∞ that␈α∞ puts␈α∞ an␈α∞ element␈α∞onto␈α∞the␈α∞end␈α∞of␈α∞a␈α∞list.␈α∂ (From␈α∞a
␈↓ ↓H␈↓strictly␈α∂list␈α∂point␈α∂of␈α∂view,␈α∂such␈α∂ a␈α⊂ function␈α∂ would␈α∂ be␈α∂ as␈α∂elementary␈α∂ as␈α∂ ␈↓αcons␈↓␈α∂ which␈α⊂puts␈α∂an
␈↓ ↓H␈↓element␈α onto␈α the␈α front␈α of␈α a␈α list,␈α but,␈α when␈α we␈α consider␈α the␈α implementation␈α of␈α lists␈α by␈α list␈α structures,
␈↓ ↓H␈↓we␈α see␈α that␈α the␈α function␈α is␈α not␈α so␈α elementary.␈α This␈α has␈α led␈α some␈α people␈α to␈α construct␈α systems␈α in
␈↓ ↓H␈↓which␈α lists␈α are␈α bi-directional,␈α but,␈α in␈α the␈α main,␈α this␈α has␈α turned␈α out␈α to␈α be␈α a␈α bad␈α idea).␈α Anyway,
␈↓ ↓H␈↓it is usually easier to recur on one argument of a function than to recur on the other.
␈↓ ↓H␈↓ It␈α∞ is␈α
often␈α∞necessary␈α∞to␈α
represent␈α∞a␈α
correspondence␈α∞between␈α∞the␈α
elements␈α∞of␈α
a␈α∞small␈α∞set␈α
of
␈↓ ↓H␈↓atoms␈α
and␈α∞certain␈α
S-expressions␈α
by␈α∞ a␈α
list␈α
structure.␈α∞ This␈α
is␈α
conveniently␈α∞done␈α
by␈α
means␈α∞of␈α
an
␈↓ ↓H␈↓association␈α list␈α which␈α is␈α a␈α list␈α of␈α pairs,␈α each␈α pair␈α consisting␈α of␈α an␈α atom␈α and␈α the␈α corresponding␈α S-
␈↓ ↓H␈↓expression. Thus the association list
␈↓ ↓H␈↓ ␈↓∧((X . (PLUS A B)) (Y . C) (Z . (TIMES U V)),
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :21
␈↓ ↓H␈↓∧␈↓which would print as
␈↓ ↓H␈↓ ␈↓∧((X PLUS A B)) (Y . C) (Z TIMES U V)),
␈↓ ↓H␈↓∧␈↓pairs␈α
␈↓∧X␈↓␈α∞ with␈α
␈↓∧(PLUS␈α
A␈α∞B),␈α
Y␈↓␈α∞ with␈α
␈↓∧C␈↓,␈α
etc.␈α∞We␈α
need␈α∞a␈α
function␈α
to␈α∞tell␈α
whether␈α∞ anything␈α
is
␈↓ ↓H␈↓associated with the atom ␈↓αx␈↓ in the association list ␈↓αa␈↓, and, if so, to tell us what. We have
␈↓ ↓H␈↓ ␈↓αassoc␈↓↓[␈↓αx, a␈↓↓] ← ␈↓βif n ␈↓αa ␈↓βthen ␈↓∧NIL ␈↓βelse if ␈↓αx ␈↓βeq aa ␈↓αa ␈↓βthen a ␈↓αa
␈↓ ↓H␈↓α␈↓ ␈↓α␈↓βelse ␈↓αassoc␈↓↓[␈↓αx, ␈↓βd ␈↓αa␈↓↓].
␈↓ ↓H␈↓↓␈↓Its␈α
value␈α
is␈α
␈↓∧NIL␈↓␈α
if␈α
nothing␈α
is␈α
associated␈α
with␈α
␈↓αx␈↓␈α
and␈α
the␈α
association␈α
pair␈α∞otherwise.␈α
E.g.
␈↓ ↓H␈↓␈↓αassoc␈↓↓[␈↓∧X, ((X.W) (Y.V))␈↓↓] = ␈↓∧(X.W)␈↓.
␈↓ ↓H␈↓ It␈α
commonly␈α
happens␈α
that␈α
a␈α
function␈α
has␈α
no␈α
simple␈α
recursion,␈α
but␈α
there␈α
is␈α
a␈α simple␈α
recursion
␈↓ ↓H␈↓for␈α⊃a␈α∩function␈α⊃with␈α⊃one␈α∩more␈α⊃variable␈α⊃that␈α∩ reduces␈α⊃ to␈α⊃the␈α∩desired␈α⊃function␈α⊃when␈α∩the␈α⊃extra
␈↓ ↓H␈↓variable is set to ␈↓∧NIL␈↓. Thus
␈↓ ↓H␈↓ ␈↓αreverse␈↓↓[␈↓αu␈↓↓] ← ␈↓αrev1␈↓↓[␈↓αx, ␈↓∧NIL␈↓↓],
␈↓ ↓H␈↓↓␈↓where
␈↓ ↓H␈↓ ␈↓αrev1␈↓↓[␈↓αu, v␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓αv ␈↓βelse ␈↓αrev1␈↓↓[␈↓βd ␈↓αu, ␈↓βa ␈↓αu . v␈↓↓].
␈↓ ↓H␈↓↓␈↓αreverse␈↓␈α has␈α a␈α
direct␈α recursive␈α definition␈α
as␈α discovered␈α by␈α S.␈α
Ness,␈α but␈α no-one␈α
would␈α want␈α to␈α use␈α
the
␈↓ ↓H␈↓following␈α∞in␈α∞actual␈α∞computation␈α∞ nor␈α∞does␈α∞ it␈α∞generate␈α∞much␈α∞understanding,␈α∞only␈α∞appreciation␈α∞of
␈↓ ↓H␈↓Mr. Ness's ingenuity:
␈↓ ↓H␈↓ ␈↓αreverse␈↓↓[␈↓αu␈↓↓] ← ␈↓βif n ␈↓αu ␈↓↓∨ ␈↓βn d ␈↓αu ␈↓βthen ␈↓αu ␈↓βelse
␈↓ ↓H␈↓β␈↓ ␈↓βa ␈↓αreverse␈↓↓[␈↓βd ␈↓αu␈↓↓] . ␈↓αreverse␈↓↓[␈↓βa ␈↓αu. reverse␈↓↓[␈↓βd ␈↓αreverse␈↓↓[␈↓βd ␈↓αu␈↓↓]]].
␈↓ ↓H␈↓ Exercises
␈↓ ↓H␈↓ 1.␈α Using␈α the␈α function␈α ␈↓αmember␈↓↓[␈↓αx,␈α u␈↓↓]␈↓␈α defined␈α in␈α Chapter␈α I␈α which␈α may␈α also␈α be␈α written␈α ␈↓αx␈α ␈↓↓ε␈α ␈↓αu␈↓,
␈↓ ↓H␈↓write␈α function␈α definitions␈α for␈α the␈α union␈α ␈↓αu␈α ␈↓↓∪␈α ␈↓αv␈↓␈α of␈α lists␈α ␈↓αu␈↓␈α and␈α ␈↓αv␈↓,␈α the␈α intersection␈α ␈↓αu␈α ␈↓↓∩␈α ␈↓αv␈↓,␈α and␈α the
␈↓ ↓H␈↓set difference ␈↓αu␈↓↓-␈↓αv␈↓. What is wanted should be clear from the examples:
␈↓ ↓H␈↓ ␈↓∧(A B C) ␈↓↓∪␈↓∧ (B C D) ␈↓↓=␈↓∧ (A B C D),
␈↓ ↓H␈↓∧␈↓ ␈↓∧(A B C) ␈↓↓∩␈↓∧ (B C D) ␈↓↓=␈↓∧ (B C),
␈↓ ↓H␈↓∧␈↓and
␈↓ ↓H␈↓ ␈↓∧(A B C) ␈↓↓-␈↓∧ (B C D) ␈↓↓=␈↓∧ (A).
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :22
␈↓ ↓H␈↓∧␈↓Pay␈α∂ attention␈α∂ to␈α∂getting␈α∂correct␈α∂the␈α∂trivial␈α∂cases␈α∂in␈α∂which␈α∂some␈α∂of␈α∂the␈α∂arguments␈α∂are␈α⊂␈↓∧NIL␈↓.␈α∂ In
␈↓ ↓H␈↓general, it is important to understand clearly the trivial cases of functions.
␈↓ ↓H␈↓ 2.␈α⊂ Suppose␈α⊂ ␈↓αx␈↓␈α⊂ takes␈α⊃ numbers␈α⊂ as␈α⊂ values␈α⊂and␈α⊂ ␈↓αu␈↓␈α⊃ takes␈α⊂as␈α⊂values␈α⊂lists␈α⊂of␈α⊃numbers␈α⊂in
␈↓ ↓H␈↓ascending␈α order,␈α
e.g.␈α ␈↓∧(2␈α
4␈α 7)␈↓.␈α
Write␈α a␈α
function␈α ␈↓αmerge␈↓↓[␈↓αx,␈α
u␈↓↓]␈↓␈α whose␈α
value␈α is␈α
obtained␈α from␈α
that
␈↓ ↓H␈↓of␈α
␈↓αu␈↓␈α
by␈α
putting␈α
␈↓αx␈↓␈α∞ in␈α
␈↓αu␈↓␈α
in␈α
its␈α
proper␈α
place.␈α∞ Thus␈α
␈↓αmerge␈↓↓[␈↓∧3,␈α
(2␈α
4)␈↓↓]␈α
=␈α
␈↓∧(2␈α∞3␈α
4)␈↓,
␈↓ ↓H␈↓and ␈↓αmerge␈↓↓[␈↓∧3, (2 3)␈↓↓] = ␈↓∧(2 3 3)␈↓.
␈↓ ↓H␈↓ 3.␈α∂ Write␈α∞ functions␈α∂ giving␈α∞the␈α∂union,␈α∞intersection,␈α∂and␈α∞set␈α∂difference␈α∞of␈α∂ordered␈α∂lists;␈α∞the
␈↓ ↓H␈↓result is wanted as an ordered list.
␈↓ ↓H␈↓ Note␈α⊂that␈α∂computing␈α⊂these␈α∂functions␈α⊂of␈α⊂unordered␈α∂lists␈α⊂ takes␈α∂a␈α⊂ number␈α⊂ of␈α∂comparisons
␈↓ ↓H␈↓proportional␈α to␈α the␈α square␈α
of␈α the␈α number␈α of␈α
elements␈α of␈α a␈α typical␈α
list,␈α while␈α for␈α ordered␈α
lists,␈α the
␈↓ ↓H␈↓number of comparisons is proportional to the number of elements.
␈↓ ↓H␈↓ 4.␈α
Using␈α
␈↓αmerge␈↓,␈α∞write␈α
a␈α
function␈α∞ ␈↓αsort␈↓␈α
that␈α
transforms␈α
an␈α∞unordered␈α
list␈α
into␈α∞an␈α
ordered
␈↓ ↓H␈↓list.
␈↓ ↓H␈↓ 5.␈α∃Write␈α⊗a␈α∃function␈α∃ ␈↓αgoodsort␈↓␈α⊗ that␈α∃ sorts␈α⊗ a␈α∃ list␈α∃ using␈α⊗ a␈α∃number␈α⊗ of␈α∃ comparisons
␈↓ ↓H␈↓proportional to ␈↓αn log n␈↓, where ␈↓αn␈↓ is the length of the list to be sorted.
␈↓ ↓H␈↓3. ␈↓βSimple S-expression recursion.␈↓
␈↓ ↓H␈↓ In␈α another␈α class␈α of␈α problems,␈α the␈α value␈α of␈α the␈α function␈α is␈α immediate␈α for␈α
atomic␈α symbols,
␈↓ ↓H␈↓and␈α∂for␈α∞non␈α∂atoms␈α∞depends␈α∂only␈α∞on␈α∂the␈α∞values␈α∂for␈α∞ the␈α∂a-part␈α∞and␈α∂the␈α∞d-part␈α∂of␈α∂the␈α∞argument.
␈↓ ↓H␈↓Thus ␈↓αsubst␈↓ was defined by
␈↓ ↓H␈↓ ␈↓αsubst␈↓↓[␈↓αx, y, z␈↓↓] ← ␈↓βif at ␈↓αz ␈↓βthen ␈↓↓[␈↓βif ␈↓αz ␈↓βeq ␈↓αy ␈↓βthen ␈↓αx ␈↓βelse ␈↓αz␈↓↓]
␈↓ ↓H␈↓↓ ␈↓βelse ␈↓αsubst␈↓↓[␈↓αx, y, ␈↓βa ␈↓αz␈↓↓] . ␈↓αsubst␈↓↓[␈↓αx , y , ␈↓βd ␈↓αz␈↓↓].
␈↓ ↓H␈↓↓␈↓ ␈↓↓␈↓Two␈α⊃other␈α∩examples␈α⊃are␈α⊃ ␈↓αequal␈↓␈α∩ which␈α⊃gives␈α⊃ the␈α∩ equality␈α⊃ of␈α⊃S-expressions␈α∩ and␈α⊃ ␈↓αflat␈↓
␈↓ ↓H␈↓which spreads an S-expression into a list of atoms: They are defined by
␈↓ ↓H␈↓ ␈↓αx␈↓↓=␈↓αy ␈↓↓← ␈↓αx ␈↓βeq ␈↓αy ␈↓↓∨ [¬␈↓βat ␈↓αx ␈↓↓∧ ¬␈↓βat ␈↓αy ␈↓↓∧ ␈↓βa ␈↓αx ␈↓↓= ␈↓βa ␈↓αy ␈↓↓∧ ␈↓βd ␈↓αx ␈↓↓= ␈↓βd ␈↓αy␈↓↓],
␈↓ ↓H␈↓↓␈↓and
␈↓ ↓H␈↓ ␈↓αflat␈↓↓[␈↓αx␈↓↓] ← ␈↓αflata␈↓↓[␈↓αx, ␈↓∧NIL␈↓↓]
␈↓ ↓H␈↓↓␈↓where
␈↓ ↓H␈↓ ␈↓αflata␈↓↓[␈↓αx, u␈↓↓] ← ␈↓βif at ␈↓αx ␈↓βthen ␈↓αx.y ␈↓βelse ␈↓αflata␈↓↓[␈↓βa ␈↓αx, flata␈↓↓[␈↓βd ␈↓αx, y␈↓↓]].
␈↓ ↓H␈↓↓␈↓ EXERCISES
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :23
␈↓ ↓H␈↓ 1.␈α Write␈α
a␈α predicate␈α to␈α
tell␈α whether␈α a␈α
given␈α atom␈α
occurs␈α in␈α a␈α
given␈α S-expression,␈α e.g.␈α
␈↓αoccur␈↓↓[␈↓∧B,
␈↓ ↓H␈↓∧((A.B).C)␈↓↓] = ␈↓∧T␈↓.
␈↓ ↓H␈↓ 2. Write a predicate to tell how many times a given atom occurs in an S-expression.
␈↓ ↓H␈↓ 3.␈α∞ Write␈α∞ a␈α∞ function␈α∞to␈α∞make␈α∞a␈α∂list␈α∞without␈α∞duplications␈α∞of␈α∞the␈α∞atoms␈α∞occurring␈α∞in␈α∂an␈α∞S-
␈↓ ↓H␈↓expression.
␈↓ ↓H␈↓ 4.␈α Write␈α a␈α
function␈α to␈α make␈α a␈α
list␈α of␈α all␈α
atoms␈α that␈α occur␈α more␈α
than␈α once␈α in␈α a␈α
given
␈↓ ↓H␈↓S-expression paired with their multiplicities.
␈↓ ↓H␈↓ 5.␈α Write␈α a␈α
predicate␈α to␈α tell␈α
whether␈α an␈α S-expression␈α
has␈α more␈α than␈α
one␈α occurrence␈α of␈α a␈α
given
␈↓ ↓H␈↓S-expression as a sub-expression.
␈↓ ↓H␈↓4. ␈↓βOther structural recursions.␈↓
␈↓ ↓H␈↓ When␈α↔lists␈α_are␈α↔used␈α_to␈α↔represent␈α_algebraic␈α↔expressions,␈α_functions␈α↔of␈α_these␈α↔algebraic
␈↓ ↓H␈↓expressions␈α⊗often␈α⊗have␈α⊗a␈α⊗recursive␈α⊗form␈α⊗closely␈α⊗related␈α⊗to␈α⊗the␈α⊗inductive␈α⊗definition␈α⊗of␈α∃the
␈↓ ↓H␈↓expressions.␈α⊂ Suppose,␈α⊂for␈α⊂example,␈α⊂that␈α⊂sums␈α⊂and␈α⊂products␈α⊂are␈α⊂represented␈α⊂respectively␈α⊂by␈α∂the
␈↓ ↓H␈↓forms␈α ␈↓∧(PLUS␈α
X␈α Y)␈↓␈α
and␈α ␈↓∧(TIMES␈α
X␈α Y)␈↓␈α
and␈α that␈α
the␈α values␈α
of␈α variables␈α
are␈α given␈α
on␈α an␈α a-list.␈α
We
␈↓ ↓H␈↓can write a recursive formula for the value of an expression as follows:
␈↓ ↓H␈↓ ␈↓αvalue␈↓↓[␈↓αe, a␈↓↓] ← ␈↓βif at ␈↓αe ␈↓βthen d ␈↓αassoc␈↓↓[␈↓αe, a␈↓↓]
␈↓ ↓H␈↓↓␈↓ ␈↓↓␈↓βelse if a ␈↓αe ␈↓βeq ␈↓∧PLUS ␈↓βthen ␈↓αvalue␈↓↓[␈↓βad ␈↓αe, a␈↓↓] + ␈↓αvalue␈↓↓[␈↓βadd ␈↓αe, a␈↓↓]
␈↓ ↓H␈↓↓␈↓ ␈↓↓␈↓βelse if a ␈↓αe ␈↓βeq ␈↓∧TIMES ␈↓βthen ␈↓αvalue␈↓↓[␈↓βad ␈↓αe, a␈↓↓] * ␈↓αvalue␈↓↓[␈↓βadd ␈↓αe, a␈↓↓].
␈↓ ↓H␈↓↓␈↓On␈α the␈α other␈α hand,␈α suppose␈α that␈α sums␈α and␈α products␈α are␈α not␈α restricted␈α to␈α have␈α just␈α two␈α arguments;
␈↓ ↓H␈↓then we must use auxiliary functions to define the value of an expression, as follows:
␈↓ ↓H␈↓ ␈↓αvalue␈↓↓[␈↓αe, a␈↓↓] ← ␈↓βif at ␈↓αe ␈↓βthen d ␈↓αassoc␈↓↓[␈↓αe, a␈↓↓]
␈↓ ↓H␈↓↓ ␈↓βelse if a ␈↓αe ␈↓βeq ␈↓∧PLUS ␈↓βthen ␈↓αvplus␈↓↓[␈↓βd ␈↓αe, a␈↓↓]
␈↓ ↓H␈↓↓ ␈↓βelse if a ␈↓αe ␈↓βeq ␈↓∧TIMES ␈↓βthen ␈↓αvtimes␈↓↓[␈↓βd ␈↓αe, a␈↓↓].
␈↓ ↓H␈↓↓␈↓where
␈↓ ↓H␈↓ ␈↓αvplus␈↓↓[␈↓αu, a␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓∧0 ␈↓βelse ␈↓αvalue␈↓↓[␈↓βa ␈↓αu, a␈↓↓] + ␈↓αvplus␈↓↓[␈↓βd ␈↓αu, a␈↓↓],
␈↓ ↓H␈↓↓␈↓and
␈↓ ↓H␈↓ ␈↓αvtimes␈↓↓[␈↓αu, a␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓∧1 ␈↓βelse ␈↓αvalue␈↓↓[␈↓βa ␈↓αu, a␈↓↓] * ␈↓αvtimes␈↓↓[␈↓βd ␈↓αu, a␈↓↓].
␈↓ ↓H␈↓↓␈↓In␈α
both␈α
cases,␈α the␈α
recursion␈α
form␈α is␈α
related␈α
to␈α the␈α
structure␈α
of␈α the␈α
algebraic␈α
expressions␈α more␈α
closely
␈↓ ↓H␈↓than to the structure of S-expressions or lists.
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :24
␈↓ ↓H␈↓5. ␈↓βTree search.␈↓
␈↓ ↓H␈↓ We␈α
begin␈α
with␈α
a␈α
general␈α
depth␈α
first␈α
tree␈α
search␈α
function.␈α
It␈α
can␈α
be␈α
used␈α
to␈α
search␈α
specific␈α
trees
␈↓ ↓H␈↓of␈α possibilities␈α by␈α defining␈α three␈α
auxiliary␈α functions␈α in␈α a␈α way␈α
that␈α depends␈α on␈α the␈α application.␈α
We
␈↓ ↓H␈↓have
␈↓ ↓H␈↓ ␈↓αsearch p ␈↓↓← ␈↓βif ␈↓αlose p ␈↓βthen ␈↓LOSE
␈↓ ↓H␈↓ ␈↓βelse if ␈↓αter p ␈↓βthen ␈↓αp ␈↓βelse ␈↓αsearchlis␈↓↓[␈↓αsuccessors p␈↓↓]␈↓
␈↓ ↓H␈↓where
␈↓ ↓H␈↓ ␈↓αsearchlis u ␈↓↓← ␈↓β if n ␈↓αu ␈↓βthen ␈↓LOSE ␈↓βelse ␈↓α␈↓↓{␈↓αsearch ␈↓βa ␈↓αu␈↓↓}[␈↓αλx␈↓↓:␈↓α ␈↓βif ␈↓αx ␈↓↓= ␈↓LOSE ␈↓βthen ␈↓αsearchlis ␈↓βd ␈↓αu ␈↓βelse ␈↓αx␈↓↓]␈↓α.␈↓
␈↓ ↓H␈↓In␈α
the␈α
applications,␈α
we␈α
start␈α
with␈α
a␈α
position␈α
␈↓αp␈↓¬0␈↓,␈α and␈α
we␈α
are␈α
looking␈α
for␈α
a␈α
win␈α
in␈α
the␈α successor␈α
tree
␈↓ ↓H␈↓of␈α ␈↓αp␈↓¬0␈↓.␈α Certain␈α positions␈α lose␈α and␈α there␈α is␈α no␈α point␈α looking␈α at␈α their␈α successors.␈α This␈α
is␈α decided
␈↓ ↓H␈↓by␈α
the␈α
predicate␈α
␈↓αlose␈↓.␈α
A␈α
position␈α
is␈α
a␈α
win␈α
if␈α
it␈α
doesn't␈α
lose␈α
and␈α
it␈α
satisfies␈α
the␈α
predicate␈α ␈↓αter␈↓.
␈↓ ↓H␈↓The␈α successors␈α of␈α a␈α position␈α is␈α given␈α by␈α
the␈α function␈α ␈↓αsuccessors␈↓,␈α and␈α the␈α value␈α of␈α ␈↓αsearch␈α
p␈↓␈α is
␈↓ ↓H␈↓the␈α⊂ winning␈α⊂position.␈α∂ No␈α⊂non-losing␈α⊂position␈α∂should␈α⊂have␈α⊂the␈α∂ name␈α⊂LOSE␈α⊂or␈α⊂the␈α∂function
␈↓ ↓H␈↓won't work properly.
␈↓ ↓H␈↓ Our␈α⊂first␈α⊂example␈α⊂is␈α⊂ finding␈α⊂a␈α⊂path␈α⊂from␈α⊂an␈α⊂ initial␈α⊂node␈α⊂to␈α⊂a␈α⊂final␈α⊂node␈α⊂ in␈α⊂a␈α⊂graph
␈↓ ↓H␈↓represented␈α
by␈α
a␈α
list␈α
structure␈α
as␈α
described␈α
in␈α chapter␈α
I.␈α
A␈α
position␈α
is␈α
a␈α
path␈α
starting␈α
from␈α the
␈↓ ↓H␈↓initial␈α
node␈α and␈α
continuing␈α
to␈α some␈α
intermediate␈α node␈α
and␈α
is␈α represented␈α
by␈α
a␈α list␈α
of␈α its␈α
nodes
␈↓ ↓H␈↓in reverse order. The three functions for this application are
␈↓ ↓H␈↓ ␈↓αlose p ␈↓↓← ␈↓βa ␈↓αp ␈↓↓ε ␈↓βd ␈↓αp,
␈↓ ↓H␈↓α␈↓ ␈↓αter p ␈↓↓← [␈↓βa ␈↓αp ␈↓↓=␈↓α final␈↓↓]␈↓α, ␈↓
␈↓ ↓H␈↓and
␈↓ ↓H␈↓ ␈↓αsuccessors p ␈↓↓←␈↓α mapcar␈↓↓[␈↓βd ␈↓αassoc␈↓↓[␈↓βa ␈↓αp, graph␈↓↓]␈↓α, λx␈↓↓:␈↓α x.p␈↓↓]␈↓α.␈↓
␈↓ ↓H␈↓ Another␈α example␈α is␈α
the␈α so-called␈α ␈↓αInstant␈α
Insanity␈↓␈α puzzle.␈α There␈α
are␈α four␈α cubical␈α
blocks,␈α and
␈↓ ↓H␈↓each␈α face␈α of␈α
each␈α block␈α is␈α
colored␈α with␈α one␈α
of␈α four␈α colors.␈α The␈α
object␈α of␈α the␈α
puzzle␈α is␈α to␈α
build␈α a
␈↓ ↓H␈↓tower␈α of␈α all␈α four␈α blocks␈α such␈α that␈α each␈α vertical␈α face␈α of␈α the␈α tower␈α involves␈α all␈α four␈α colors.␈α In␈α order
␈↓ ↓H␈↓to␈α∞use␈α∂the␈α∞above␈α∂defined␈α∞function␈α∂␈↓αsearch␈↓␈α∞for␈α∂this␈α∞purpose,␈α∂we␈α∞must␈α∂define␈α∞the␈α∂representation␈α∞of
␈↓ ↓H␈↓positions␈α and␈α give␈α the␈α functions␈α ␈↓αlose,␈α ter,␈α ␈↓and␈α ␈↓αsuccessors␈↓.␈α A␈α position␈α is␈α represented␈α by␈α a␈α list␈α of␈α lists
␈↓ ↓H␈↓¬␈α⊂one␈α⊂for␈α⊂each␈α∂face␈α⊂of␈α⊂the␈α⊂tower.␈α∂ Each␈α⊂sublist␈α⊂is␈α⊂the␈α∂list␈α⊂of␈α⊂colors␈α⊂of␈α∂the␈α⊂faces␈α⊂of␈α⊂the␈α∂blocks
␈↓ ↓H␈↓showing␈α in␈α
that␈α face.␈α
We␈α shall␈α assume␈α
that␈α the␈α
blocks␈α are␈α described␈α
in␈α the␈α
following␈α longwinded
␈↓ ↓H␈↓but␈α convenient␈α way.␈α (We'll␈α take␈α up␈α precomputing␈α this␈α description␈α later.)␈α For␈α each␈α block␈α there␈α is␈α a
␈↓ ↓H␈↓list␈α∞of␈α
the␈α∞24␈α∞orientations␈α
of␈α∞the␈α
block␈α∞where␈α∞each␈α
orientation␈α∞is␈α
described␈α∞as␈α∞a␈α
list␈α∞of␈α∞the␈α
colors
␈↓ ↓H␈↓around␈α the␈α vertical␈α faces␈α of␈α the␈α block␈α when␈α it␈α is␈α in␈α that␈α orientation.␈α Thus␈α the␈α puzzle␈α is␈α described
␈↓ ↓H␈↓by a list of lists of lists which we shall call ␈↓αpuzz␈↓.
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :25
␈↓ ↓H␈↓ We now have
␈↓ ↓H␈↓ ␈↓αp␈↓¬0␈↓ ␈↓↓=␈↓ (NIL NIL NIL NIL),
␈↓ ↓H␈↓ ␈↓αlose p ␈↓↓←␈↓α orlis␈↓↓[␈↓αp, λu␈↓↓:␈↓α ␈↓βa ␈↓αu ␈↓↓ε ␈↓βd ␈↓αu␈↓↓]␈↓α,
␈↓ ↓H␈↓α␈↓ ␈↓αter p ␈↓↓← [␈↓αlength ␈↓βa ␈↓αp ␈↓↓=␈↓α 4␈↓↓]␈↓,
␈↓ ↓H␈↓and
␈↓ ↓H␈↓ ␈↓αsuccessors p ␈↓↓←␈↓α mapcar␈↓↓[␈↓βa ␈↓αnth␈↓↓[␈↓αpuzz, 1 + length ␈↓βa ␈↓αp␈↓↓]␈↓α , λx␈↓↓:␈↓α mapcar2␈↓↓[␈↓αp, x, λyz␈↓↓:␈↓α z.y␈↓↓]]␈↓α, ␈↓
␈↓ ↓H␈↓where
␈↓ ↓H␈↓ ␈↓αmapcar2␈↓↓[␈↓αu, v, f␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓NIL ␈↓βelse f␈↓↓[␈↓βa ␈↓αu, ␈↓βa ␈↓αv␈↓↓]␈↓α . mapcar2␈↓↓[␈↓βd ␈↓αu, ␈↓βd ␈↓αv, f␈↓↓]␈↓α.␈↓
␈↓ ↓H␈↓ Getting␈α
the␈α initial␈α
position␈α
in␈α the␈α
desired␈α form␈α
is␈α
as␈α complicated␈α
a␈α computation␈α
as␈α
the␈α actual
␈↓ ↓H␈↓tree␈α∞search.␈α∞ It␈α∞can␈α∞be␈α∞conveniently␈α∞done␈α∞by␈α∞a␈α∞sequence␈α∞of␈α∞assignment␈α∞statements␈α∞starting␈α∞with␈α
a
␈↓ ↓H␈↓description of the blocks:
␈↓ ↓H␈↓ ␈↓αpuzz1 ␈↓↓← ␈↓((G B B W R G) (G G B G W R) (G W W R B R) (G G R B W W)).
␈↓ ↓H␈↓Here␈α each␈α block␈α is␈α represented␈α by␈α a␈α list␈α of␈α the␈α colors␈α of␈α the␈α faces␈α starting␈α with␈α the␈α top␈α face,␈α going
␈↓ ↓H␈↓around the sides in a clockwise direction and finishing with the bottom face.
␈↓ ↓H␈↓ We␈α need␈α to␈α go␈α from␈α this␈α description␈α of␈α the␈α blocks␈α to␈α a␈α list␈α of␈α the␈α possible␈α cycles␈α of␈α colors␈α on
␈↓ ↓H␈↓the␈α
vertical␈α
faces␈α
for␈α the␈α
24␈α
orientations␈α
of␈α the␈α
block.␈α
This␈α
not␈α
easy,␈α because␈α
the␈α
order␈α
in␈α which␈α
we
␈↓ ↓H␈↓have␈α∞given␈α
the␈α∞colors␈α∞is␈α
not␈α∞invariant␈α
under␈α∞rotations␈α∞of␈α
the␈α∞block.␈α
An␈α∞easy␈α∞way␈α
out␈α∞is␈α∞to␈α
start
␈↓ ↓H␈↓with␈α a␈α block␈α whose␈α faces␈α are␈α assigned␈α the␈α numbers␈α 1␈α thru␈α 6␈α starting␈α with␈α the␈α top,␈α going␈α clockwise
␈↓ ↓H␈↓around␈α the␈α sides␈α and␈α
finishing␈α with␈α the␈α bottom.␈α
We␈α write␈α down␈α one␈α
cycle␈α of␈α side␈α colors␈α
for␈α each
␈↓ ↓H␈↓choice␈α of␈α the␈α
face␈α put␈α on␈α
top␈α and␈α get␈α the␈α
list␈α of␈α all␈α
24␈α cycles␈α by␈α
appending␈α the␈α results␈α of␈α
generating
␈↓ ↓H␈↓the cyclic permutations of the cycles. All this is accomplished by the assignment
␈↓ ↓H␈↓ ␈↓αpuzz2 ␈↓↓←␈↓α cycles␈↓↓[␈↓(2 3 4 5)␈↓↓]␈↓␈↓↓*␈↓␈↓αcycles␈↓↓[␈↓α(␈↓(2 5 4 3)␈↓↓]␈↓␈↓↓*␈↓ ␈↓αcycles␈↓↓[␈↓α(1 2 6 4)␈↓↓]␈↓α
␈↓ ↓H␈↓α ␈↓↓*␈↓αcycles␈↓↓[␈↓α(1 4 6 2)␈↓↓]␈↓α␈↓↓*␈↓αcycles␈↓↓[␈↓α(1 3 6 5)␈↓↓]␈↓α␈↓↓*␈↓αcycles␈↓↓[␈↓α(1 5 6 3)␈↓↓]␈↓α, ␈↓
␈↓ ↓H␈↓where the function ␈↓αcycles␈↓ is defined by
␈↓ ↓H␈↓ ␈↓αcycles u ␈↓↓←␈↓α maplist␈↓↓[␈↓αu, λx␈↓↓:␈↓α x␈↓↓*␈↓αupto␈↓↓[␈↓αu, x␈↓↓]]␈↓
␈↓ ↓H␈↓with the auxiliary function
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :26
␈↓ ↓H␈↓ ␈↓αupto␈↓↓[␈↓αu, x␈↓↓] ← ␈↓βif ␈↓αx ␈↓βeq ␈↓αu ␈↓βthen ␈↓NIL ␈↓βelse a ␈↓αu . upto␈↓↓[␈↓βd ␈↓αu, x␈↓↓]␈↓α.␈↓
␈↓ ↓H␈↓Next␈α
we␈α
create␈α
for␈α
each␈α block␈α
a␈α
list␈α
of␈α
substitutions␈α
expressing␈α the␈α
colors␈α
of␈α
the␈α
six␈α numbered␈α
faces.
␈↓ ↓H␈↓We have
␈↓ ↓H␈↓ ␈↓αpuzz3 ␈↓↓←␈↓α mapcar␈↓↓[␈↓αpuzz1, λx␈↓↓:␈↓α prup␈↓↓[␈↓(1 2 3 4 5 6), ␈↓αx␈↓↓]]␈↓α, ␈↓
␈↓ ↓H␈↓and we use these substitutions to get for each block the list of 24 orientations of the block. Thus
␈↓ ↓H␈↓ ␈↓αpuzz4 ␈↓↓←␈↓α mapcar␈↓↓[␈↓αpuzz3, λs␈↓↓:␈↓α sublis␈↓↓[␈↓αs, puzz3␈↓↓]]␈↓α.
␈↓ ↓H␈↓αpuzz4␈↓␈α
has␈α all␈α
24␈α
orientations␈α of␈α
the␈α
first␈α block␈α
while␈α for␈α
symmetry␈α
reasons␈α we␈α
need␈α
only␈α consider
␈↓ ↓H␈↓three as distinct, say the first, ninth, and seventeen. So we finally get
␈↓ ↓H␈↓ ␈↓αpuzz ␈↓↓← (␈↓βa ␈↓αnth␈↓↓[␈↓βa ␈↓αpuzz4, 1␈↓↓] ␈↓βa ␈↓αnth␈↓↓[␈↓βa ␈↓αpuzz4, 9␈↓↓] ␈↓βa ␈↓αnth␈↓↓[␈↓βa ␈↓αpuzz4, 17␈↓↓]) . ␈↓βd ␈↓αpuzz4.␈↓
␈↓ ↓H␈↓The program when compiled runs about 11 seconds on the PDP-10.
␈↓ ↓H␈↓ A␈α
more␈α
sophisticated␈α∞representation␈α
of␈α
face␈α∞cycles␈α
and␈α
partial␈α
towers␈α∞makes␈α
a␈α
factor␈α∞of␈α
ten
␈↓ ↓H␈↓speedup␈α
without␈α changing␈α
the␈α basic␈α
search␈α algorithm.␈α
A␈α face␈α
cycle␈α is␈α
represented␈α by␈α
16␈α bits␈α
in␈α a
␈↓ ↓H␈↓word␈α four␈α for␈α each␈α face␈α a␈α
particular␈α one␈α of␈α which␈α being␈α turned␈α on␈α
tells␈α us␈α the␈α color␈α of␈α the␈α face.␈α
If
␈↓ ↓H␈↓we␈α ␈↓βor␈↓␈α these␈α words␈α together␈α for␈α the␈α blocks␈α in␈α a␈α partial␈α tower␈α we␈α get␈α a␈α word␈α which␈α tells␈α us␈α for␈α each
␈↓ ↓H␈↓face␈α of␈α the␈α tower␈α what␈α colors␈α have␈α been␈α used.␈α A␈α particular␈α face␈α cycle␈α from␈α the␈α next␈α block␈α can␈α be
␈↓ ↓H␈↓added␈α⊂to␈α⊂the␈α⊂tower␈α⊂if␈α⊃the␈α⊂␈↓βand␈↓␈α⊂of␈α⊂its␈α⊂word␈α⊂with␈α⊃the␈α⊂word␈α⊂representing␈α⊂the␈α⊂tower␈α⊂is␈α⊃zero.␈α⊂ We
␈↓ ↓H␈↓represent␈α a␈α position␈α by␈α a␈α list␈α of␈α words␈α representing␈α its␈α partial␈α towers␈α with␈α 0␈α as␈α the␈α last␈α element␈α
and
␈↓ ↓H␈↓the␈α highest␈α partial␈α tower␈α
as␈α the␈α first␈α element.␈α
The␈α virtue␈α of␈α this␈α
representation␈α is␈α that␈α it␈α makes␈α
the
␈↓ ↓H␈↓description␈α of␈α the␈α algorithm␈α short.␈α The␈α initial␈α position␈α is␈α (0).␈α The␈α new␈α ␈↓αpuzz␈↓␈α can␈α be␈α formed␈α from
␈↓ ↓H␈↓the old one by the assignment
␈↓ ↓H␈↓ ␈↓αpuzza ␈↓↓←␈↓α mapcar␈↓↓[␈↓αpuzz, λx␈↓↓:␈↓α mapcar␈↓↓[␈↓αx, zap␈↓↓]]␈↓α, ␈↓
␈↓ ↓H␈↓where
␈↓ ↓H␈↓ ␈↓αzap v ␈↓↓← ␈↓βif n ␈↓αv ␈↓βthen ␈↓∧0 ␈↓βelse ␈↓αpoo ␈↓βa ␈↓αv ␈↓↓+ 16 * ␈↓αzap ␈↓βd ␈↓αv, ␈↓
␈↓ ↓H␈↓and
␈↓ ↓H␈↓ ␈↓αpoo x ␈↓↓← ␈↓βif ␈↓αx␈↓↓=␈↓R ␈↓βthen ␈↓α1 ␈↓βelse if ␈↓αx␈↓↓=␈↓W ␈↓βthen ␈↓2 ␈↓βelse if ␈↓αx␈↓↓=␈↓G ␈↓βthen ␈↓4 ␈↓βelse ␈↓8.
␈↓ ↓H␈↓Now we need the new functions ␈↓αlose, ter, ␈↓and ␈↓αsuccessors␈↓. These are
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :27
␈↓ ↓H␈↓ ␈↓αlose p ␈↓↓← ␈↓βfalse␈↓α,
␈↓ ↓H␈↓α␈↓ ␈↓αter p ␈↓↓← [␈↓αlength p ␈↓↓=␈↓α 5␈↓↓]␈↓α, ␈↓
␈↓ ↓H␈↓and
␈↓ ↓H␈↓ ␈↓αsuccessors p ␈↓↓←␈↓α mapchoose␈↓↓[␈↓βa ␈↓αnth␈↓↓[␈↓αpuzza, length p␈↓↓]␈↓α, λx␈↓↓:␈↓α ␈↓βa ␈↓αp ␈↓βand ␈↓αx ␈↓↓=␈↓α 0, λx␈↓↓:␈↓α ␈↓↓[␈↓βa ␈↓αp ␈↓βor ␈↓αx␈↓↓]␈↓α . p␈↓↓]␈↓α.␈↓
␈↓ ↓H␈↓where
␈↓ ↓H␈↓ ␈↓αmapchoose␈↓↓[␈↓αu, pred, fn␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓NIL
␈↓ ↓H␈↓ ␈↓βelse if ␈↓αpred ␈↓βa ␈↓αu ␈↓βthen ␈↓αfn␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α . mapchoose␈↓↓[␈↓βd ␈↓αu , pred, fn␈↓↓] ␈↓β
␈↓ ↓H␈↓β␈↓ ␈↓βelse ␈↓αmapchoose␈↓↓[␈↓βd ␈↓αu, pred, fn␈↓↓]␈↓α.␈↓
␈↓ ↓H␈↓␈↓αlose␈↓␈α
is␈α∞trivial,␈α
because␈α
the␈α∞␈↓αmapchoose␈↓␈α
is␈α∞used␈α
to␈α
make␈α∞sure␈α
that␈α
only␈α∞non-losing␈α
new␈α∞positions␈α
are
␈↓ ↓H␈↓generated␈α∂by␈α⊂␈↓αsuccessors␈↓.␈α∂ This␈α⊂version␈α∂runs␈α⊂in␈α∂a␈α∂little␈α⊂less␈α∂than␈α⊂one␈α∂second␈α⊂on␈α∂the␈α⊂PDP-10.␈α∂ A
␈↓ ↓H␈↓greater␈α∩speedup␈α∩can␈α⊃be␈α∩made␈α∩by␈α∩the␈α⊃application␈α∩of␈α∩some␈α⊃mathematics.␈α∩ In␈α∩fact,␈α∩with␈α⊃enough
␈↓ ↓H␈↓mathematics, extensive tree search is unnecessary in this problem.
␈↓ ↓H␈↓ ␈↓αsearch␈↓␈α∂is␈α∂used␈α∞when␈α∂we␈α∂want␈α∞to␈α∂search␈α∂a␈α∂tree␈α∞of␈α∂possibilities␈α∂for␈α∞a␈α∂solution␈α∂to␈α∂a␈α∞problem.
␈↓ ↓H␈↓What␈α if␈α we␈α want␈α to␈α find␈α all␈α solutions␈α to␈α a␈α problem?␈α This␈α can␈α be␈α done␈α with␈α a␈α function␈α ␈↓αallsol␈↓␈α that
␈↓ ↓H␈↓uses the same ␈↓αlose, ter, ␈↓and ␈↓αsuccessors␈↓ functions as does ␈↓αsearch␈↓. The simplest way to write ␈↓αallsol␈↓ is
␈↓ ↓H␈↓ ␈↓αallsol p ␈↓↓← ␈↓βif ␈↓αlose p ␈↓βthen ␈↓NIL ␈↓βelse if ␈↓αter p ␈↓βthen ␈↓α(p) ␈↓βelse ␈↓αmapapp␈↓↓[␈↓αsuccessors p, allsol␈↓↓]␈↓α, ␈↓
␈↓ ↓H␈↓where
␈↓ ↓H␈↓ ␈↓αmapapp␈↓↓[␈↓αu, fn␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓NIL ␈↓βelse ␈↓αfn␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α . mappap␈↓↓[␈↓βd ␈↓αu, fn␈↓↓]␈↓α.␈↓
␈↓ ↓H␈↓This␈α form␈α of␈α
the␈α function␈α is␈α somewhat␈α
inefficient␈α because␈α of␈α all␈α
the␈α ␈↓αappend␈↓ing.␈α A␈α
more␈α efficient
␈↓ ↓H␈↓form uses an auxiliary function as follows:
␈↓ ↓H␈↓ ␈↓αallsol p ␈↓↓←␈↓α allsola␈↓↓[␈↓αp, ␈↓NIL␈↓↓]␈↓
␈↓ ↓H␈↓ ␈↓αallsola␈↓↓[␈↓αp, found␈↓↓] ← ␈↓βif ␈↓αlose p ␈↓βthen ␈↓αfound
␈↓ ↓H␈↓α ␈↓βelse if ␈↓αter p ␈↓βthen ␈↓αp . found
␈↓ ↓H␈↓α ␈↓βelse ␈↓αallsolb␈↓↓[␈↓αsuccessors p, found␈↓↓]␈↓α,
␈↓ ↓H␈↓α allsolb␈↓↓[␈↓αu, found␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓αfound ␈↓βelse ␈↓αallsolb␈↓↓[␈↓βd ␈↓αu, allsola␈↓↓[␈↓βa ␈↓αu, found␈↓↓]]␈↓α.␈↓
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :28
␈↓ ↓H␈↓The␈α∩recursive␈α⊃program␈α∩structure␈α⊃that␈α∩arises␈α⊃here␈α∩is␈α∩common␈α⊃when␈α∩a␈α⊃list␈α∩is␈α⊃to␈α∩be␈α∩formed␈α⊃by
␈↓ ↓H␈↓recurring through a list structure.
␈↓ ↓H␈↓6. ␈↓βGame trees.␈↓
␈↓ ↓H␈↓ The␈α∂positions␈α∂that␈α⊂can␈α∂be␈α∂reached␈α⊂from␈α∂an␈α∂initial␈α⊂position␈α∂in␈α∂a␈α⊂ game␈α∂ form␈α∂ a␈α⊂ tree,␈α∂and
␈↓ ↓H␈↓deciding␈α what␈α move␈α to␈α make␈α often␈α involves␈α searching␈α this␈α tree.␈α However,␈α game␈α trees␈α are␈α searched
␈↓ ↓H␈↓in␈α a␈α different␈α way␈α than␈α the␈α trees␈α we␈α have␈α looked␈α at,␈α because␈α the␈α opposing␈α interests␈α of␈α the␈α players
␈↓ ↓H␈↓makes␈α
it␈α
not␈α a␈α
search␈α
for␈α
a␈α joint␈α
line␈α
of␈α
play␈α that␈α
will␈α
lead␈α
to␈α the␈α
first␈α
player␈α
winning,␈α but
␈↓ ↓H␈↓rather a search for a strategy that will lead to a win regardless of what the other player does.
␈↓ ↓H␈↓ The␈α simplest␈α situation␈α is␈α characterized␈α by␈α a␈α function␈α ␈↓αsuccessors␈↓␈α that␈α gives␈α the␈α positions
␈↓ ↓H␈↓that␈α can␈α be␈α reached␈α in␈α one␈α move,␈α a␈α predicate␈α ␈↓αter␈↓␈α that␈α tells␈α when␈α a␈α position␈α is␈α to␈α be␈α regarded
␈↓ ↓H␈↓as␈α_ terminal␈α↔ for␈α_ the␈α_ given␈α↔ analysis,␈α_ and␈α↔ a␈α_ function␈α_␈↓αimval␈↓␈α↔ that␈α_ gives␈α_ a␈α↔ number
␈↓ ↓H␈↓approximating␈α the␈α value␈α of␈α the␈α
position␈α to␈α one␈α of␈α the␈α
players.␈α We␈α shall␈α call␈α this␈α player␈α
the
␈↓ ↓H␈↓maximizing␈α player␈α and␈α his␈α opponent␈α the␈α minimizing␈α player.␈α Usually,␈α the␈α numerical␈α values␈α arise,
␈↓ ↓H␈↓because␈α∂the␈α⊂search␈α∂cannot␈α⊂be␈α∂carried␈α∂ out␈α⊂to␈α∂the␈α⊂end␈α∂of␈α∂the␈α⊂game,␈α∂and␈α⊂the␈α∂analysis␈α⊂stops␈α∂with
␈↓ ↓H␈↓reasonably␈α static␈α
positions␈α that␈α can␈α
be␈α evaluated␈α
by␈α some␈α rule.␈α
Naturally,␈α the␈α function␈α
␈↓αimval␈↓
␈↓ ↓H␈↓is␈α
chosen␈α to␈α
be␈α
easy␈α to␈α
calculate␈α and␈α
to␈α
correlate␈α well␈α
with␈α
the␈α probability␈α
that␈α the␈α
maximizing
␈↓ ↓H␈↓player can win the position.
␈↓ ↓H␈↓ The␈α simplest␈α rule␈α for␈α finding␈α the␈α correct␈α move␈α in␈α a␈α position␈α uses␈α auxiliary␈α functions␈α ␈↓αvalmax␈↓
␈↓ ↓H␈↓and␈α ␈↓αvalmin␈↓␈α
that␈α give␈α a␈α
value␈α to␈α a␈α
position␈α by␈α
using␈α ␈↓αimval␈↓␈α if␈α
the␈α position␈α is␈α
terminal␈α and␈α taking␈α
the
␈↓ ↓H␈↓max or min of the successor positions otherwise.
␈↓ ↓H␈↓ For␈α this␈α we␈α want␈α functions␈α for␈α getting␈α the␈α maximum␈α or␈α the␈α minimum␈α of␈α a␈α function␈α on␈α a␈α
list,
␈↓ ↓H␈↓and they are defined as follows:
␈↓ ↓H␈↓ ␈↓αmaxlis␈↓↓[␈↓αu, f␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓α-␈↓↓∞␈↓α ␈↓βelse ␈↓α max␈↓↓[␈↓αf␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α, maxlis␈↓↓[␈↓βd ␈↓αu, f␈↓↓]]␈↓α, ␈↓
␈↓ ↓H␈↓and
␈↓ ↓H␈↓ ␈↓αminlis␈↓↓[␈↓αu, f␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓α␈↓↓∞␈↓α ␈↓βelse ␈↓α min␈↓↓[␈↓αf␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α, minlis␈↓↓[␈↓βd ␈↓αu, f␈↓↓]]␈↓α.␈↓
␈↓ ↓H␈↓In␈α these␈α
functions,␈α -␈↓↓∞␈↓␈α and␈α
␈↓↓∞␈↓␈α represent␈α numbers␈α
that␈α are␈α
smaller␈α and␈α larger␈α
than␈α any␈α actual␈α
values
␈↓ ↓H␈↓that␈α will␈α
occur␈α in␈α
evaluating␈α ␈↓αf␈↓.␈α
If␈α these␈α
numbers␈α are␈α
not␈α available,␈α
then␈α it␈α
is␈α necessary␈α
to␈α prime␈α
the
␈↓ ↓H␈↓function␈α∩with␈α∩the␈α∩values␈α∩of␈α∩␈↓αf␈↓␈α∩applied␈α∩to␈α∪the␈α∩first␈α∩element␈α∩of␈α∩the␈α∩list,␈α∩and␈α∩the␈α∪functions␈α∩are
␈↓ ↓H␈↓meaningless␈α for␈α null␈α lists.␈α Iterative␈α versions␈α of␈α the␈α functions␈α are␈α generally␈α better;␈α we␈α give␈α only␈α the
␈↓ ↓H␈↓iterative version of ␈↓αmaxlis␈↓, namely
␈↓ ↓H␈↓ ␈↓αmaxlis␈↓↓[␈↓αu, f␈↓↓] ←␈↓α maxlisa␈↓↓[␈↓αu, -␈↓↓∞␈↓α, f␈↓↓]␈↓α, ␈↓
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :29
␈↓ ↓H␈↓where
␈↓ ↓H␈↓ ␈↓αmaxlisa␈↓↓[␈↓αu, x, f␈↓↓] ← ␈↓αif n u ␈↓βthen ␈↓αx ␈↓βelse ␈↓αmaxlisa␈↓↓[␈↓βd ␈↓αu, max␈↓↓[␈↓αx, f␈↓↓[␈↓βa ␈↓αu␈↓↓]]␈↓α, f␈↓↓]␈↓α.␈↓
␈↓ ↓H␈↓We now have
␈↓ ↓H␈↓ ␈↓αvalmax p ␈↓↓← ␈↓βif ␈↓αter p ␈↓βthen ␈↓αimval p ␈↓βelse ␈↓αmaxlis␈↓↓[␈↓αsuccessors p, valmin␈↓↓]␈↓,
␈↓ ↓H␈↓and
␈↓ ↓H␈↓ ␈↓αvalmin p ␈↓↓← ␈↓βif ␈↓αter p ␈↓βthen ␈↓αimval p ␈↓βelse ␈↓αminlis␈↓↓[␈↓αsuccessors p, valmax␈↓↓]␈↓.
␈↓ ↓H␈↓The best move is now chosen by
␈↓ ↓H␈↓ ␈↓αmovemax p ␈↓↓←␈↓α bestmax␈↓↓[␈↓αsuccesors p, valmin␈↓↓]␈↓α, ␈↓
␈↓ ↓H␈↓or
␈↓ ↓H␈↓ ␈↓αmovemin p ␈↓↓←␈↓α bestmin␈↓↓[␈↓αsuccesors p, valmax␈↓↓]␈↓α, ␈↓
␈↓ ↓H␈↓where
␈↓ ↓H␈↓ ␈↓αbestmax␈↓↓[␈↓αu, f␈↓↓] ←␈↓α bestmaxa␈↓↓[␈↓βd ␈↓αu, ␈↓βa ␈↓αu, f␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α, f␈↓↓]␈↓α,
␈↓ ↓H␈↓α␈↓ ␈↓αbestmaxa␈↓↓[␈↓αu, sofar, valsofar, f␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓αsofar
␈↓ ↓H␈↓α ␈↓βelse if ␈↓αf␈↓↓[␈↓βa ␈↓αu␈↓↓] ≤ ␈↓αbestsofar ␈↓βthen ␈↓αbestmaxa␈↓↓[␈↓βd ␈↓αu, sofar, bestsofar, f␈↓↓]␈↓α
␈↓ ↓H␈↓α␈↓ ␈↓α␈↓βelse ␈↓αbestmaxa␈↓↓[␈↓βd ␈↓αu, ␈↓βa ␈↓αu, f␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α, f␈↓↓]␈↓α,
␈↓ ↓H␈↓α␈↓ ␈↓αbestmin␈↓↓[␈↓αu, f␈↓↓] ←␈↓α bestmina␈↓↓[␈↓βd ␈↓αu, ␈↓βa ␈↓αu, f␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α, f␈↓↓]␈↓α, ␈↓
␈↓ ↓H␈↓and
␈↓ ↓H␈↓ ␈↓αbestmina␈↓↓[␈↓αu, sofar, valsofar, f␈↓↓] ← ␈↓βif n ␈↓αu ␈↓βthen ␈↓αsofar
␈↓ ↓H␈↓α ␈↓βelse if ␈↓αf␈↓↓[␈↓βa ␈↓αu␈↓↓] ≥ ␈↓αbestsofar ␈↓βthen ␈↓αbestmina␈↓↓[␈↓βd ␈↓αu, sofar, bestsofar, f␈↓↓]␈↓α
␈↓ ↓H␈↓α␈↓ ␈↓α␈↓βelse ␈↓αbestmina␈↓↓[␈↓βd ␈↓αu, ␈↓βa ␈↓αu, f␈↓↓[␈↓βa ␈↓αu␈↓↓]␈↓α, f␈↓↓]␈↓α.␈↓
␈↓ ↓H␈↓ However,␈α
this␈α
straight␈α minimax␈α
computation␈α
of␈α the␈α
best␈α
move␈α does␈α
much␈α
more␈α computation␈α
in
␈↓ ↓H␈↓general than is usually necessary. The simplest way to see this is from the move tree of Figure 2.6.
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :30
␈↓"␈↓ ↓H␈↓ ␈↓ ¬H ≤ 8
␈↓"␈↓ ↓H␈↓ ␈↓ ¬H max ≤'
␈↓"␈↓ ↓H␈↓ ␈↓ ¬H '␈↓ ↓H αααα 1␈↓ ↓H ≤≥
␈↓"␈↓ ↓H␈↓ ␈↓ ¬H min ≤' `≥
␈↓"␈↓ ↓H␈↓ ␈↓ ¬H ≤' ` 6
␈↓"␈↓ ↓H␈↓ ␈↓ ¬H '␈↓ ↓H ≥
␈↓"␈↓ ↓H␈↓ ␈↓ ¬H `≥ ≤ 9
␈↓"␈↓ ↓H␈↓ ␈↓ ¬H `≥ ≤'
␈↓"␈↓ ↓H␈↓ ␈↓ ¬H `'␈↓ ↓H αααα X␈↓ ↓H ≥
␈↓"␈↓ ↓H␈↓ ␈↓ ¬H `≥
␈↓"␈↓ ↓H␈↓ ␈↓ ¬H ` X
␈↓ ↓H␈↓␈↓ ε␈↓ Figure 2.6␈↓
␈↓ ↓H␈↓We see from this figure that it is unnecessary to examine the moves marked
␈↓ ↓H␈↓x, because their values have no effect on the value of the game or on the
␈↓ ↓H␈↓correct move since the presence of the 9 is sufficient information at this
␈↓ ↓H␈↓point to show that the move leading to the vertex preceding it should not
␈↓ ↓H␈↓be chosen by the minimizing player.
␈↓ ↓H␈↓ The general situation is that it is unnecessary to examine further
␈↓ ↓H␈↓moves in a position once a move is found that refutes moving to the
␈↓ ↓H␈↓position in the first place. This idea is called the αβ-heuristic and
␈↓ ↓H␈↓expressed in the following recursive definitions:
␈↓ ↓H␈↓ ␈↓αmaxval p ␈↓↓←␈↓α maxval1␈↓↓[␈↓αp, -␈↓↓∞␈↓α, ␈↓↓∞␈↓α␈↓↓]␈↓α,
␈↓ ↓H␈↓α maxval1␈↓↓[␈↓αp, α, β␈↓↓] ← ␈↓βif ␈↓αter p ␈↓βthen ␈↓αmax␈↓↓[␈↓αα, min␈↓↓[␈↓αβ, imval p␈↓↓]]␈↓α
␈↓ ↓H␈↓α ␈↓βelse ␈↓αmaxval2␈↓↓[␈↓αsuccessors p, α, β␈↓↓]␈↓α,
␈↓ ↓H␈↓α maxval2␈↓↓[␈↓αu, α, β␈↓↓] ← {␈↓αminval1␈↓↓[␈↓βa ␈↓αu, α, β␈↓↓]}[␈↓αλw␈↓↓:␈↓α ␈↓βif ␈↓αw ␈↓↓=␈↓α β ␈↓βthen
␈↓ ↓H␈↓β ␈↓αβ ␈↓βelse ␈↓αmaxval2␈↓↓[␈↓βd ␈↓αu, w, β␈↓↓]]␈↓α,
␈↓ ↓H␈↓α␈↓ ␈↓αminval p ␈↓↓←␈↓α minval1␈↓↓[␈↓αp, -␈↓↓∞␈↓α, ␈↓↓∞␈↓α␈↓↓]␈↓α,
␈↓ ↓H␈↓α minval1␈↓↓[␈↓αp, α, β␈↓↓] ← ␈↓βif ␈↓αter p ␈↓βthen ␈↓αmax␈↓↓[␈↓αα, min␈↓↓[␈↓αβ, imval p␈↓↓]]␈↓α
␈↓ ↓H␈↓α ␈↓βelse ␈↓αminval2␈↓↓[␈↓αsuccessors p, α, β␈↓↓]␈↓α,
␈↓ ↓H␈↓α minval2␈↓↓[␈↓αu, α, β␈↓↓] ← {␈↓αmaxval1␈↓↓[␈↓βa ␈↓αu, α, β␈↓↓]}[␈↓αλw␈↓↓:␈↓α ␈↓βif ␈↓αw ␈↓↓=␈↓α α ␈↓βthen
␈↓ ↓H␈↓β ␈↓αα ␈↓βelse ␈↓αminval2␈↓↓[␈↓βd ␈↓αu, α, w␈↓↓]␈↓α.␈↓
␈↓ ↓H␈↓ The reduction in number of positions examined given by the αβ algorithm
␈↓ ↓H␈↓over the simple minimax algorithm depends on the order in which the moves are
␈↓ ↓H␈↓examined. In the worst case, the moves happen to be examined in inverse order
␈↓ ↓H␈↓of merit in every position on the tree, i.e. the worst move first. In that case,
␈↓ ↓H␈↓there is no improvement over minimax. The best case is the one in which the
␈↓ ↓H␈↓␈↓ ¬rCHAPTER II␈↓ :31
␈↓ ↓H␈↓best move in every position is examined first. If we look ␈↓αn␈↓ moves
␈↓ ↓H␈↓deep on a tree that has ␈↓αk␈↓ successors to each position, then minimax looks
␈↓ ↓H␈↓at ␈↓αk␈↓εn␈↓ positions while αβ looks at about only ␈↓αk␈↓εn/2␈↓. Thus a
␈↓ ↓H␈↓program that looks at 10␈↓ε4␈↓ moves with αβ might have to look at 10␈↓ε8␈↓
␈↓ ↓H␈↓with minimax. For this reason, game playing programs using αβ make a big
␈↓ ↓H␈↓effort to include as good as possible an ordering of moves into the ␈↓αsuccessors␈↓
␈↓ ↓H␈↓function. When there is a deep tree search to be done, the way to make the
␈↓ ↓H␈↓ordering is with a short look-ahead to a much smaller depth than the main
␈↓ ↓H␈↓search. Still shorter look-aheads are used deeper in the tree, and beyond
␈↓ ↓H␈↓a certain depth, non-look-ahead ordering methods are of decreasing complexity.
␈↓ ↓H␈↓ A version of αβ incorporating optimistic and pessimistic evaluations
␈↓ ↓H␈↓of positions was first proposed by McCarthy about 1958. Edwards and Hart at
␈↓ ↓H␈↓M.I.T. about 1959 proved that the present version of αβ works and calculated the
␈↓ ↓H␈↓improvement it gives over minimax. The first publication, however, was
␈↓ ↓H␈↓Brudno (1963). It is worth noting that αβ was not used in the early chess
␈↓ ↓H␈↓playing programs in spite of the fact that it is clearly used in any human
␈↓ ↓H␈↓play. Its non-use, therefore, represents a failure of self-observation.
␈↓ ↓H␈↓Very likely, there are a number of other algorithms used in human thought
␈↓ ↓H␈↓that we have not noticed an incorporated in our programs. To the extent
␈↓ ↓H␈↓that this is so, artificial intelligence will be ␈↓αa posteriori␈↓ obvious
␈↓ ↓H␈↓even though it is ␈↓αa priori␈↓ very difficult.